perm filename DESCR[RDG,DBL]13 blob
sn#620187 filedate 1981-10-28 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00018 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 RLL TALK
C00005 00003 Add/Change to memo, next iteration:
C00009 00004 Short description (for AAAI Article)
C00015 00005 Version of Short PCohen rewrote (June 1980) [Taken from previous page]
C00018 00006 Mailed to NII (LENAT/CC) 18:50 26-June
C00029 00007 Mailed to CSD.NII@SCORE 15:41 3-July
C00041 00008 Received from NII 7-July (essentially final form)
C00051 00009 Sent to DBL fr NLM report - 10 April 1981
C00064 00010 Comparison to Editors
C00066 00011 Language metaphor
C00070 00012 Ref:
C00073 00013 ∂4 Apr 1981 1605-PST CSD.GENESERETH mrs report
C00084 00014 ∂ 14 Jul 1981 2254-PDT KAPLAN at SRI-AI Origins of MRS
C00091 00015 [RLL Section of BES Book - Original - sent to DBL, thence to Waterman]
C00140 00016 [My version, after fix up (after Don, after DBL,from me)]
C00207 00017 RLL subChapter in BES book
C00230 00018 [DBL's version, from last page]
C00302 ENDMK
C⊗;
RLL TALK
Hillel metaphor:
"Tell me what's in the Torah, while I stand on one foot."
other fellow -> go away
Hillel -> "Do not do ... " The rest is just example and ...
Similarly what is in RLL-1 is just simple, single idea:
Leave parts of the representation explicit, and modifiable --
using same formalism as what is conventionally called "data".
The rest of just implementation.
This talk will first provide motivation -- why this is a good idea, and
why and how it can, at all, work.
Then specifics of RLL-1 ...
<<Table with missing leg for Problem 1; Hammer and Nail for Soln (rep'n lang)>>
<<Broken cup for Problem 2; Glue for Soln (rep'n lang)>>
Let us pause here and ask why LISP is in such common usage --
what advantages does it have over, say, Fortran (well, we know why not
Fortran) over, say, Pascal or the other "good" (structured) languages?
Answer is clear - Lisp is flexible and adaptable to new situations.
How does this happen: LISP code is identical, in form, to the data
it can use -- they are all S-Expressions. And LISP knows how to deal
with S-expressions in general, and hence can modify code with the
same ease as it can manipulate data in general.
Add/Change to memo, next iteration:
0. Page numbers - there should be a blank page after the title.
1. Glossary:
Language, Representation, Rep'n Language, Semantics
rll, RLL-1,
Slot Type, slot, unit, proposition, class of units, typical member, defaults
2. Example of RLL in action - perhaps spill problem (with its control process)
3. Move much of Section 4.3 (example of defining a new type of slot using HLDefn)
to Appendix A, so this just points there.
4. Further details
FAST-CACHE, FAST-GET for GetValue
Fast-Cache for CacheValue
Fast-Put for PutValue
Add on ways of handling quantification
[Maybe Mike's 13 facts]
Note at end that we are changing it so each unit (well, each KB) knows how to
access its slots, ...
Section numbers of Appendix F, about Functions, mislabeled (with D.2, ...)
"Developped"
Enough for PRIMER - i.e. minimal set of commands the user must know.
(Anne's suggestion)
Present FIRST as static interpreter, then go on to show how that might be changed.
Westfold, Steve [mispelled ...]
What is our purpose -- i.e.
Verification - RLL is a success when ____.
i) Given any new rep'n item, we can nod our head, realizing it could be done
ii) Others abandon their systems, realizing RLL's generality subsumes
such systems
In overview:
There is one major distinction between what the name r..l..l.. implies, and
what this system really is and does. When you modify some part of the
networks which describes/represents VLSI, you do NOT produce a new chip --
that is, the referent of these symbols is, of course, unchanged.
Changes to RLL-1, however, may have more far ranging effects -- the system
itself (that is, what these various symbols are actually describing) are
changed by commands to RLL-1. Like Dorian Grey, changing these symbols
causes their extensions to be altered.
Add: ref to Music Encycl, for Bach; also Dorian Grey
Precise Statement of our goals -
To develop a body of mechanisms (read language) in which one can
represent the components of a RL, and their interactions.
(Components include:
Slots, Inheritance Mechanism, Matchers, Verifiers, ?Semantics? )
Include hierarchy of existing pieces - taken from Klone, KRL, ...,
user can pick and choose
Note it is NOT required that we (explicitly) encode every possible rep'nal
construct -- our goal is to be able to develope such, readily.
Short description (for AAAI Article)
Implementing a complex AI task using begins by designing and building a
suitable representation language, in which to express the primitives of
this domain are easy to express and manipulate. (eg Parsing Trees for NL,
or Experiment Planning for MOLGEN.) The representation language used in
one domain is very seldom borrowed and adaptated to serve for some other
application -- the facilities which were desirable assets for the original
task become limitations elsewhere. Most such languages are therefore
built essentially from scratch -- a very time consuming (and, we believe,
avoidable) task.
Realizing this problem, we built a language in which the components of a
representation language could be described and built, and integrated into
a new representation language. This Representation Language Language,
RLL, provides a body of high level constructs which the user can apply
when designing his new language, [significantly speeding up this first
step.] RLL includes a large library of "representational pieces", e.g.
including the mode of inheritance used by the Examples link of the Units
package, or the A-Kind-Of type of slot associated with FRL. A novice user
can easily design his system by simply choosing the precise amalgamation
of these pieces he wishes. RLL is then responsible for meshing these
parts together, to form a coherent and working whole.
A more advanced user can exploit RLL's mechanisms for designing new parts
-- for example, a new inheritance, or new type of format permissable for a
slot. He could then use these in the system he is building. Once again,
the use of high level operators (such as Create-New-Inheritance-Like(
InstanceOf )) will vastly lessen the time required to construct this
desired language (compared to using, say, CAR, CDR and COND).
While several people have expressed interest in using RLL for their
applications, the system has only recently become sufficiently stable to
permit others to use it. It has been involved in two small, internal
tasks -- an adventure game simulation and an exploration into a more
complete self-description of various of its parts, using lower-level
primitives.
This research has forced us to examine a variety of issues -- ranging from
"what's in a language" concerns, which asks just what are the constituent
parts of a representation language, to epistomological questions, such as
how to handle intentional objects, or syntactic slots.
The details of how RLL was designed can be found in [Greiner 1980]; and
our proposals for solving many of the outstanding issues and questions are
in [Greiner and Lenat 1980] and [Genesereth and Lenat 1980]. Finally,
Dave Smith's demand paging system, CORLL, frees RLL from InterLisp's 256K
storage limitation.
Ref:
Genesereth, Micheal, and Lenat, Douglas B., "?", HPP Working Paper 80-?,
June 1980.
Greiner, Russell, "A Representation Language
Language", HPP Working Paer 80-9.
Greiner, Russell and Lenat, Douglas B., "A Representation Language
Language", submitted to this AAAI.
Smith, David E., "CORLL: A Demand Paging System for Units", HPP Working
Paper 80-8, June 1980.
Version of Short PCohen rewrote (June 1980) [Taken from previous page]
Implementing a complex AI task often begins by designing and
building a suitable representation language, in which the primitives
of the domain are easy to express and manipulate. The representation
language used in one domain is seldom borrowed and adapted to
another, because the facilities that were assets for one task become
limitations elsewhere. For this reason, most such languages are built
from scratch. The goal of the RLL effort is to reduce the amount of
time expended in building a representation language, by providing a
Representation Language Language, that is, a language that provides
the user with the components of many representation languages, and
with the ability to integrate them. RLL contains a large library of
"representational pieces", for example, the mode of inheritance used
by the Examples link of the Units package, or the A-Kind-Of type of
slot used in the MIT Frames Representation Language, FRL. A novice
user can easily design a language simply by picking an amalgamation
of pieces; RLL is responsible for meshing them together into a
coherent and working whole. A more advanced user can exploit RLL's
mechanisms for designing new parts, for example, a new mode of
inheritance, or a new type of format for a slot. He could then use
these in the system he is building. The use of high level operators
(e.g. "Create-New-Inheritance-Like(Instance-Of)") will greatly lessen
the time required to construct the desired language.
The RLL system is an ongoing effort. It has recently been
used in two small, internal tasks, an adventure game simulation and
an exploration into a more complete self-description of various of
its parts, using lower level primitives.
Mailed to NII (LENAT/CC) 18:50 26-June
Short description (for NII's HPP Brochure)
Motivation
Implementing a complex AI task usually begins by building such a
representation language. This language is designed to facilitate the
expression and manipulation of the primitives of this particular domain.
Experience has shown that the language used in one domain is seldom
borrowed and adaptated to serve for some other application: The
facilities which were desirable assets for the original task become
limitations elsewhere. Most such languages are built essentially from
scratch -- a very time consuming (and, we believe, avoidable) task.
Task Description
To speed up this first step, we built a language which "knows" about the
components of representation languages in general. This Representation
Language Language, RLL, provides an extendable collection of high level
operators and constructs, which can be used to describe and build such
components. It can then integrate these pieces into a functional, new
representation language. The user can use these functions to design his
"personal" language, capable of dealing with the problems associated with
his specfic domain and application.
RLL's open-ended means there were be an extendable set of possible
representational pieces. The current system knows about slots, modes of
inheritance, specification for functions, etc. (Much of the nomenclature,
such as Unit and Slot, is taken from the UNITS package, described
earlier.) (A sample mode of inheritance is the one associated with the
Examples link of the Units package, which corresponds to "element-of".)
Most operators are methods for defining or refining such pieces. For
example, RLL allows the user to define the "Parents" slot as the union of
the "Mother" and "Father" slots -- that is, (the value of) the "Parents"
slot of an individual is a list consisting of (the value of) that person's
"Mother" slot, and (the value of) his "Father" slot. This brief
definition alone is sufficient to tell RLL everything it needs to know
about this slot. RLL will automatically invalidate the value stored for
Fred's parents if his mother remarries; and know that only some units may
have a Parents slots (viz. those which had both a Mother and Father slot
-- i.e. people).
RLL includes a large library of pre-fabricated "representational pieces".
In fact, a novice can easily design his language by simply choosing the
precise amalgamation of these pieces he wishes. RLL will then mesh these
parts together, to form a coherent and working whole.
A more advanced user can exploit RLL's mechanisms for designing new parts.
The "Father" example above illustrates the ease associated with defining a
new slot; designing a new inheritance, or new type of format is as easy.
As before, the host of high level operators considerably lessens the
complexity associated with constructing and integrating this new piece.
Using these parts (however they were derived,) as tools, the user can then
procede with his main task. If he later discovers limitations in this set
of facilities, he need only redesign the offending components. RLL's high
level operators make such modifications easy to perform; furthermore, RLL
will automatically perform any necessary reformatting of the existing data
to conform to this new, just defined set of conventions.
Current Applications
While several people have expressed interest in using RLL for their
applications, the system has only recently become sufficiently stable to
permit others to use it. It has been involved in two small, internal
tasks -- an adventure game simulation and an exploration into a more
complete self-description of various of its parts, using lower-level
primitives.
An brief overview of RLL's goals can be found in [Greiner & Lenat]. This
is expanded in [Greiner 1980], which illustrating many additional aspects
of RLL's design and implementation. Finally, an important stand-alone
submodule of RLL is its demand paging system, CORLL, which frees RLL from
InterLisp's 256K storage limitation. (See [Smith 1980].)
Ref:
Greiner, Russell, "A Representation Language Language", HPP Working Paper
80-9, June 1980.
Greiner, Russell and Lenat, Douglas B., "A Representation Language
Language", AAAI Conference, Stanford, 1980.
Smith, David E., "CORLL: A Demand Paging System for Units", HPP Working
Paper 80-8, June 1980.
∂Date: 27 Jun 1980 1442-PDT
From: Nii at SUMEX-AIM
Subject: Re: Short RLL Description
To: RDG at SU-AI
cc: lenat
In response to your message sent 26 Jun 1980 1850-PDT
Russ,
The piece you wrote is really nice and is much appreciated.
I'll go over it Doug to get his ok
penny
-------
∂Date: 3 Jul 1980 1119-PDT
From: CSD.NII at SU-SCORE
Subject: RLL article
To: csd.greiner at SU-SCORE, rdg at SU-AI
cc: csd.nii at SU-SCORE
I've fixed the first 2-3 paragraphs of the RLL article. It is
unprotected and is in my directory at SCORE (do not use the one
at Sumex) <csd.nii>broch.rll. We are fast reaching a deadline so
could you get it back to me as soon as possible.
penny
-------
∂Date: 6 Jul 1980 1403-PDT - Nii at SUMEX-AIM - Rll write-up
To: rdg at SU-AI
cc: nii, Lenat
Russ,
I did some text editing to the version you gave me to save time.
I don't believe I changed any meanings intended in the paper. Please
look is over and see if you are satisfied--it's in <nii>broch.rll@sumex.
Meta-comments
1. Try to avoid too many parenthetical remarks. They are reserved for
statements which can be skipped over. Either something is worth
saying or it isn't. I took out most of the parentheses and made them
into regular text.
2. Unnecesary uses of "this" and "that"'s. Since the text progression
is quite logical, I replaced most of them with "the" or repeated the
references.
3. Look out for parallel constructs--avoid split infinitives.
4. Use commas, ;, and -- appropriately.
Since English is my second language, I'm not the one to criticize other's
English. However, there are some heuristics that can be learned that
might make your writing task a little easier and smoother.
penny
-------
Mailed to NI@SUMEX (& LENAT/cc) 13:03 7-July
Penny,
That document seemed good. I have (only) a few suggsted modifications;
our words do seem to be converging. One more iteration? When?
Russ
Mailed to CSD.NII@SCORE 15:41 3-July
Motivation
RLL is a tool to facilitiate the building of expert programs quickly. It
is itself an expert program, whose domain of expertise is knowledge
representation.
Task Description
The standard first step taken in building an application program (in AI)
is the design and implementation of a language which will be used
represent the knowledge this program will use. Experience has shown that
the language developed in one application is seldom adaptated for use in
other programs. The features that were useful for the original problem
become limitations elsewhere. Thus, a specialized representation language
is redesigned and reimplemented for each application -- a very time
consuming task.
RLL (Representation Language Language) is designed to reduce the time
spent building such representation languages. It is a language which
"knows" about the components of representation languages in general. It
provides the user with an extendable collection of high level operators
and constructs which he can use to describe and build components of his
target language. After the user has specified the desirable features of
the target language, RLL integrates these components into a functional,
new representation language. In other words, a user can readily (and
rapidly) design a personalized language, exactly suited to the domain and
the application task at hand.
RLL's open-ended means there were be an extendable set of possible
representational pieces. The current system can deal with pieces such as
slots, modes of inheritance, and specification for functions. Slots
conform to the definition given in the UNITS package description,
appearing earlier. (In fact, RLL borrowed much of its nomenclature, as
well as software, from this system. [Footnote: One example is a
stand-alone submodule of RLL, which implements a demand paging system.
This frees RLL from InterLisp's 256K storage limitation. (See [Smith].])
UNITs also motivated an important mode of inheritance: the one associated
with its Examples link. (This relationship corresponds to set theory
notion of "element-of".) There is nothing in UNITS which corresponds to
our use of functional specification. We are currently exploring this
domain, which helps unify many outwardly diverse concepts, such as
processes, mechanisms, and slots.
The initial RLL system is itself a very versatile representation language.
For most tasks, the user can use it as he might any other representation
language. What distinguishes RLL is that the user is not forced to follow
the constraints imposed by this particular language; instead, he can mold
his copy of RLL to accomodate his particular task.
RLL derives this flexibility in two ways. First, RLL contains a large
library of largely independent, pre-fabricated "representational pieces".
For example, there are many (mutually incompatible) ways in which one can
associate facts with an object. One corresponds to UNIT's idea of a slot,
while another is to let each unit point the list of assertions in which it
is involves. (Consider how to represent "Fred is the Father of Mary".
Using slots, this means filling the "Father" slot of the unit Mary with
the value "Fred". In the second notation, the unit Mary would point to
the assertion "(Father Mary Fred)".) This first method, using explicit
slots, is "active" in the initial RLL system. If this proves
unsatifactory, a simple command will instruct RLL to switch to this second
system. From then on, (or, at least, until the user's next alterring
command,) this modified version of RLL will understand this different set
of instructions, and its reactions will follow this second convention.
Furthermore, RLL will automatically convert the user's existing data into
this new format.
To effectively use these varied components, RLL must "understand" what
each does, and how. This information allows RLL to mesh diverse parts
together, to form a coherent and working whole. As such, it should be
possible for the user to design a fairly arbitrary language by simply
choosing the precise amalgamation of these pieces he wishes; leaving to
RLL the responsibility, and headaches, of fitting them together.
Realizing this catalog of "chunks" will never be totally complete, RLL's
second approach towards generality are its collection of tools designed to
help the user fabricate new parts. These high-level operators can be used
to define a new component, (or type of component) or refine an existing
one.
For example, the user can define the "Parents" slot as the union of the
"Mother" and "Father" slots. That is, (the value of) the "Parents" slot
of an individual is a list consisting of (the values of) that person's
"Mother" and "Father" slots. This brief definition (Parent = Union(Mother
Father) ) is sufficient to tell RLL everything it needs to know about this
slot. RLL now knows to (automatically) invalidate the value stored for
Fred's parents if his mother remarries; and know that only some units may
have a Parents slots (viz. those which had both a Mother and Father slot
-- i.e. people).
Defining a new slot is trivial; designing a new inheritance, or new type
of format is as easy. The host of high-level operators considerably
lessens the complexity associated with constructing and integrating this
new piece.
These parts (however they were derived,) become the language the user can
use for his main task. If he later discovers limitations in this set of
facilities, he need only replace, or redesign the offending components.
RLL's collection of types of parts, and its high-level operators, make
either type of modification relatively simple. As shown above, RLL then
does the "busywork" -- such as reformatting the existing data to conform
to this new set of conventions.
Current Applications
While several people have expressed interest in using RLL for their
applications, the system has only recently become sufficiently stable to
permit others to use it. It has been involved in two small, internal
tasks -- an adventure game simulation and an exploration into a more
complete self-description of various of its parts, using lower-level
primitives.
An brief overview of RLL's goals can be found in [Greiner & Lenat]. This
is expanded in [Greiner], which illustrating many additional aspects of
RLL's design and implementation.
Ref:
Greiner, Russell, "A Representation Language Language", HPP Working Paper
80-9, July 1980.
Greiner, Russell and Lenat, Douglas B., "A Representation Language
Language", AAAI Conference, August 1980, Stanford.
Smith, David E., "CORLL: A Demand Paging System for Units", HPP Working
Paper 80-8, July 1980.
Received from NII 7-July (essentially final form)
RLL
Motivation
RLL is a tool to facilitiate the building of expert programs
quickly. It is itself an expert program, whose domain of expertise
is knowledge representation.
Task Description
The standard first step taken in building an application
program in AI is the design and implementation of a language that
(in which to)
represents the knowledge the program will use. Experience has shown
that the language developed in one application is seldom adaptated
for use in other programs. The features that were useful for the
original problem become limitations elsewhere. Thus, a specialized
representation language is redesigned and reimplemented for each
application -- a very time consuming task.
RLL (Representation Language Language) is designed to reduce
the time spent building such representation languages. It is a
language which "knows" about the components of representation
languages in general. It provides the user with an extendable
collection of high level operators and constructs which he can use to
describe and build components of his target language. After the user
has specified the desirable features of the target language, RLL
integrates these components into a functional, new representation
language. In other words, a user can readily and rapidly design a
personalized language, exactly suited to the domain and the
application task at hand.
RLL is an open-ended language in which the user can add pieces
of language not provided in RLL's standard repetoir. Currently RLL
can deal with pieces such as slots, modes of inheritance, and
specification of functions. Slots conform to the definition given in
the UNITS package (see page ). In fact, RLL borrowed much of its
nomenclature, as well as software, from UNITS. For example, it uses
one of UNITS main mode of inheritance, the Example link. This
inheritance relationship corresponds to set theory notion of
"element-of". However, there is nothing in UNITS which corresponds
to RLL's use of functional specification. This domain is currently
being explored, because it would help unify many outwardly diverse
concepts, such as processes, mechanisms, and slots.
The initial RLL system is itself a very versatile
representation language. For most tasks, the user can use it as he
might any other representation language. What distinguishes RLL is
that the user is not forced to follow the constraints imposed by a
particular language; instead, he can mold his copy of RLL to
accomodate his particular task.
RLL derives this flexibility in two ways. First, RLL
contains a large library of largely independent, pre-fabricated
"representational pieces". For example, there are many (mutually
incompatible) ways in which one can associate facts with an object.
One corresponds to UNIT's idea of a slot, while another is the use of
pointer to a list or relevant assertions. For example, consider how
to represent "Fred is the Father of Mary". Using slots, "Father"
slot of the unit Mary would be filled with the value "Fred". Using
links, the unit Mary would point to the assertion "(Father Mary
Fred)". The first method, using explicit slots, is "active" in the
initial RLL system. If this proves unsatifactory, a simple command
will instruct RLL to switch to the second method. From then on,
(or, at least, until the user's next alterring command) the user
modified version of RLL will prevail. Furthermore, RLL will
automatically convert the user's existing data into the new format.
To effectively use the variety of components, RLL must
"understand" what each does, and how. This information allows RLL to
mesh diverse parts together to form a coherent and workable whole.
As such, it should be possible for the user to design a fairly
arbitrary language by simply choosing the precise amalgamation of the
pieces he needs, leaving to RLL the responsibility of fitting them
together.
Cataloging of possible components will never be totally
complete. RLL's second approach towards generality is its collection
of tools designed to help the user fabricate new parts. A set of
high-level operators are provided so that the user can define new
components or a type of components, or refine existing ones.
For example, the user can define the "Parents" slot as the
union of the "Mother" and "Father" slots. That is, the value of the
"Parents" slot of an individual is a list consisting of the values of
that person's "Mother" and "Father" slots. This brief definition,
Parent = Union(Mother Father), is sufficient to tell RLL everything it
needs to know about this slot. RLL now knows to automatically
invalidate the value stored for Fred's parents if his mother
remarries. Furthermore it knows that only some units may have a
Parents slots, i.e. those which have both a Mother and Father slots.
(Hence while each person or zebra should have parents, we should not
expect a VLSI chip to have such a slot, nor the unit representing the
class of functions.)
The language parts, however they were derived, become the
language the user can use for his task. If he later discovers
limitations in this set he need only replace or redesign the
offending components. RLL's collection of types of parts, and its
high-level operators, make modifications relatively simple. As shown
above, RLL then does the "busywork", such as reformatting the
existing data to conform to the set of new conventions.
Current Status
Although interests have been expressed in using RLL for a
variety of applications, the system has only recently become
sufficiently stable to permit others to use it. Thus far, it has
been used in two small internal tasks (an adventure game simulation
and an exploration into a more complete self-description of its
various parts using lower-level primitives,) and one still trivial
task, which dealt with oil spills (see Hayes-Roth et al.).
Sent to DBL fr NLM report - 10 April 1981
1. What else will be in this report - the unit's package?
2. What formatting system? SCRIBE?
3. Purpose of this report - to convince others of RLL's utility,
or demonstrate its abilities, or ...
In 1/2 page...
Feel free to subset this to the size you wish.
RLL
Motivation
RLL is a tool to facilitiate the building of expert programs
quickly. It is itself an expert program, whose domain of expertise
is knowledge representation.
Task Description
The standard first step taken in building an application
program in AI is the design and implementation of a language
in which to
represents the knowledge the program will use. Experience has shown
that the language developed in one application is seldom adaptated
for use in other programs -- the features that were useful for the
original problem become limitations elsewhere. Thus, a specialized
representation language is redesigned and reimplemented for each
application -- a very time consuming task.
RLL (Representation Language Language) is designed to reduce
the time spent building such representation languages. It is a
language which "knows" about the components of representation
languages in general. It provides the user with an extendable
collection of high level operators and constructs which he can use to
describe and build components of his target language. After the user
has specified the desirable features of the target language, RLL
integrates these components into a functional, new representation
language. In other words, a user can readily and rapidly design a
personalized language, exactly suited to the domain and the
application task at hand.
RLL is an open-ended language in which the user can add pieces
of language not provided in RLL's standard repetoir. Currently RLL
can deal with pieces such as slots, modes of inheritance, and
specification of functions. Slots conform to the definition given in
the UNITS package (see page ?). In fact, RLL borrowed much of its
nomenclature, as well as software, from UNITS. For example, it uses
one of UNITS main mode of inheritance, the Example link. This
inheritance relationship corresponds to set theory notion of
"element-of". However, there is nothing in UNITS which corresponds
to RLL's use of functional specification. This domain is currently
being explored, because it would help unify many outwardly diverse
concepts, such as processes, mechanisms, and slots.
The initial RLL system is itself a very versatile
representation language. For most tasks, the user can use it as he
might any other representation language. What distinguishes RLL is
that the user is not forced to follow the constraints imposed by a
particular language; instead, he can mold his copy of RLL to
accomodate his particular task.
RLL derives this flexibility in two ways. First, RLL
contains a large library of largely independent, pre-fabricated
"representational pieces". For example, there are many (mutually
incompatible) ways in which one can associate facts with an object.
One corresponds to UNIT's idea of a slot, while another is the use of
pointer to a list or relevant assertions. For example, consider how
to represent "Fred is the Father of Mary". Using slots, "Father"
slot of the unit Mary would be filled with the value "Fred". Using
links, the unit Mary would point to the assertion "(Father Mary
Fred)". The first method, using explicit slots, is "active" in the
initial RLL system. If this proves unsatifactory, a simple command
will instruct RLL to switch to the second method. From then on,
(or, at least, until the user's next alterring command) the user
modified version of RLL will prevail. Furthermore, RLL will
automatically convert the user's existing data into the new format.
To effectively use the variety of components, RLL must
"understand" what each does, and how. This information allows RLL to
mesh diverse parts together to form a coherent and workable whole.
As such, it should be possible for the user to design a fairly
arbitrary language by simply choosing the precise amalgamation of the
pieces he needs, leaving to RLL the responsibility of fitting them
together.
Cataloging of possible components will never be totally
complete. RLL's second approach towards generality is its collection
of tools designed to help the user fabricate new parts. A set of
high-level operators are provided so that the user can define new
components or a type of components, or refine existing ones.
For example, the user can define the "Parents" slot as the
union of the "Mother" and "Father" slots. That is, the value of the
"Parents" slot of an individual is a list consisting of the values of
that person's "Mother" and "Father" slots. This brief definition,
Parent = Union(Mother Father), is sufficient to tell RLL everything it
needs to know about this slot. RLL now knows to automatically
invalidate the value stored for Fred's parents if his mother
remarries. Furthermore it knows that only some units may have a
Parents slots, i.e. those which have both a Mother and Father slots.
(Hence while each person or zebra should have parents, we should not
expect a VLSI chip to have such a slot, nor the unit representing the
class of functions.)
The language parts, however they were derived, become the
language the user can use for his task. If he later discovers
limitations in this set he need only replace or redesign the
offending components. RLL's collection of types of parts, and its
high-level operators, make modifications relatively simple. As shown
above, RLL then does the "busywork", such as reformatting the
existing data to conform to the set of new conventions.
Current Status
Although interests have been expressed in using RLL for a
variety of applications, the system has only recently become
sufficiently stable to permit others to use it.
RLL's power can be seen in the variety of tasks in which it has been employed:
an adventure game simulation
an (internal) exploration towards a more complete self-description of its
various parts using lower-level primitives,
and a complex task in which RLL assumed the role
of expert-system builder, designing a program to
handle with oil spills (see Hayes-Roth et al.).
Bibliography
@InProceedings(RLL,
Key = "Greiner",
Author = "Greiner, Russell and Lenat, Douglas B.",
Title = "A Representation Language Language",
Booktitle = "1-AAAI",
Organization = SU,
Month = AUG, Year = 1980)
@TechReport(RLLa,
Key = "Greiner",
Author = "Greiner, Russell",
Title = "RLL-1: A Representation Language Language",
Number = "HPP-80-9",
Type = WP,
Institution = CSDSU,
Month = OCT, Year = 1980)
@TechReport(RLLb,
Key = "Greiner",
Author = "Greiner, Russell and Lenat, Douglas B.", Title = "Details of RLL-1",
Number = "HPP-80-23",
Type = WP,
Institution = CSDSU,
Month = OCT, Year = 1980)
@Manual(MRS,
Key = "Genesereth",
Author = "Genesereth, Micheal, Greiner, Russell, and Smith, David",
Title = "MRS Manual",
Note = "HPP Working Paper HPP-80-24", Month = DEC, Year = 1980)
@UnPublished(ExpertSystems,
Key = "Hayes-Roth",
Author = "Hayes-Roth, Frederick, Waterman, D. A. and Lenat, Douglas B.",
Title = "Designing Expert Systems", Note = "in construction")
@Manual(Units,
Key = "Smith",
Author = "Smith, Reid G. and Friedland, Peter",
Title = "Unit Package User's Guide",
Month = DEC, Year = 1980,
Note = "(HPP-80-28, and Defence Research Establishment Atlantic # 80/L)")
Comparison to Editors
Units :: Bravo
- Each does somethings very nicely, but cannot be extended
or modified -- interpreted designed for limited (and known to be
constrained) set of tasks.
KRL :: E
- Both try for universality, and both fail for the same reason:
The interpreter cannot be changed. Although other effects can be
simulated, that's as close as one can get.
ROSIE :: IBM's Editor
- Both were designed to be learned easily, and to be inextendable.
(Rosie's aims differ slightly from Unit's:
Rosie's purpose is for each of understanding; as opposed to
representational generality -- Units avoids these linguistic issues
for the most part.)
RLL-1 :: EMACS
- Both are very general languages, designed to be modified (and to
facilitate such modifications). Both establish some initial
conventions: RLL-1 has slots, EMACS is defined exclusively for screen
displays.
MRS :: TECO
- Both are bare-bones -- just enough to get started, and to be massaged
into the form desired.
(Note EMACS can be [in fact, was] written in TECO.)
Language metaphor
Representation Languages share many similiarities with natural languages,
such as English.
Both can be used to express facts about the world,
and in both cases, such descriptions are in terms of very high level, and "natural"
units.
Both are open-ended, and extendable --
new terms can be formed from old, using various established methods.
(New words can be created by adding a prefix to an existing word.
One can infer the meaning of "verbifying", as it applies a standard
method by verbifying to the noun, "verb".
Also, a word can take on a new, or extended meaning,
by using it in a new context.)
A language is more than just a dictionary of words;
it also includes a grammar which describes
how to use words to form higher level constructs,
such as Noun Phrase, Sentence, or Story.
RLL is like a very general purpose language,
which contains a large number of words, and a very encompassing grammar.
Many users will be able to use this, sans alterations.
What distinquishes RLL from most other representational languages is its
ability to change.
It can built not only new words,
but new and different grammars as well.
Most systems impose a fairly rigid set of conventions on what they can do,
and how.
The user has no choice but to conform to these standards,
which forces some applications into awkward contortions, if it is at all possible.
It achieves this generality by describing these each of notions precisely;
representing them within RLL's own formalisms
(much like reading an text on English, written in English).
These descriptions can then be used.
A user can combine the desired features
of several distinct languages to form
a new, specialized language, suited to his particular needs and goals.
Our eventual goal is to provide an entire catalog of these language
provides the ability to shift amoung languages -- to use German's
capability to string nouns together, and
Ref:
Extensible langauge, for describing extensibilites:
Davis, Randall, "Generalized procedure calling and content-directed invocation",
SIGPLAN Noices, Vol. 12, Nol 8, August 1977, pp. 45-54
Same general ideas - of bootstrapping down & down
Sandewall, Erik, "?", IJCAI 4
Smalltalk - idea of each unit knowing what to do
Fahlman "<10% not easy to represent, and require special fixes"
[see IJCAI-79, p.282 - in article re: AMORD]
Fox (IJCAI-79 282-4) - make things as explicit as possible - and declarative
Georgeff (IJCAI-79 330) - can add semantics to MetaRules easily
[use Cogn Econ to decide what needs to be recomputed]
Laubsh (IJCAI-79 516) [W German] {ATN w/Sem Nets} put concepts into Units,
with additional facts
Leitner, Henry H (Harvard) & Micheal W Freeman(Burroughs), (IJCAI-79 525)
store with "slot" what to do
Miller, G.A., E. Galanter, and K H Pribaum "Plans & the Structure of Behaviour,
New York: Holt, Rinehard & Winston, 1960. (see IJCAI-79 555)
"Major source of new plans is old plans."
Mostow & Hayes-Roth (IJCAI-79 601) - schema for heuristic search, w/slots for facts
IJCAI-79, 617 - AKO limiting - as meaning too many things, and all imprecisely
Semantics not pure (618)
"Prespecitifed useages of attached procedures is too restrictive"
(but they still stop shrt of real soln - ie they add own (deepter) conventions)
Hayes "Defense of Logic" - refers to building an interpreter for the interpreter
[see also Stefik's HPP-80-13, appearing in ?Artificial Intelligence? 1980]
∂4 Apr 1981 1605-PST CSD.GENESERETH mrs report
To: csd.greiner
I thought you might be interested in the progress report I gave Doug.
It includes an intro paragraph that reflects my best effort at
presenting a view of the coordination between the MRS and RLL efforts.
Look out! Here it comes.
Our research in knowledge representation has largely focussed
on the problem of giving a system knowledge of itself and the ability
to control its operation and modify its structure. Two outgrowths of
this research are the Modifiable Representation System MRS and the
Representation Language Language RLL. MRS is a minimal
self-descriptive system with the ability to reason about its own
structure and behavior. RLL is intended to have more extensive
knowledge about knowledge representation and thereby facilitate the
tailoring the system for partiular applications. MRS is much smaller
than RLL and is conceived of as the core from which the more
knowledgeable RLL will eventually be built. Superficially, MRS
differs from RLL in its external language (full predicate calculus
rather than "units") and in the specific capabilities available (e.g.
general backward chaining).
MRS - A Modifiable Representation System
As a knowledge representation system in its own right, MRS is
intended for use by AI researchers in building expert systems. It
offers a repertory of commands for asserting and retrieving
information, with varying degrees of inference. Information is
entered in a predicate calculus-like language of assertions and is
stored in either a propositional network or any of a variety of
specialized data representations (e.g. property lists, alists, bit
vectors). The initial system includes a vocabulary of concepts and
facts about logic, sets, mappings, arithmetic, and procedures.
What makes MRS special among knowledge representation systems
is its ability to deal with itself in the same way that it deals with
application domains (like geology and medicine). In MRS, the basic
representation is described within the representation itself, and the
inference techniques used in reasoning about application domains can
be applied to reasoning about the system. For example, MRS might use
facts about sets and sequences to determine whether a statement is
provable, or it might use facts about directed graphs to determine
that backward chaining is the most appropriate technique to use with
forward branching search spaces.
Because of MRS's formalism and meta-level vocabulary, it's
possible for a user to ask the system questions about itself; and,
since the system has a partial self-description, it can answer many of
these questions. More importantly, the system uses its own
description in carrying out each operation. The upshot is that the
user can affect MRS's behavior simply by modifying this description.
With a few simple statements, it is possible to select a new data
structure (e.g. property lists) or enable a different inference
algorithm (e.g. a general procedure like property inheritance or backward
chaining or a domain specific procedural attachment).
Furthermore, MRS is fully modifiable, i.e. it can be
converted into any LISP program by making assertions within its own
formalism (hence the name "Modifiable Representation System"). Most
knowledge representation systems were developed in the context of
particular applications, e.g. KRL and OWL in natural language and
Units in molecular biology. The problem is that what is good for one
application is usually not perfect for another. Although most systems
offer their users a number of options, there are often undesirable
design decisions that cannot be changed. In MRS modifiability is a
design goal, which is realized by the system's self-descriptive vocabulary
and its handling of changes in its own description.
Of course, bare Lisp is also fully modifiable. One important
difference is that MRS's language is more general than Lisp's, allowing its
user to assert arbitrary facts in the predicate calculus as well as defining
procedures. Furthermore, the transformation to other knowledge representation
systems is facilitated by the knowledge about knowledge representation built
into larger systems like RLL.
State of Implementation and Use
The core of MRS is fully implemented in DEC-20 Maclisp and
Interlisp and will soon be available in Franz Lisp on the Vax and
Interlisp on the Xerox Dolphin. A separate effort is underway to
implement the system in IBM's LISP370. MRS is being used in a variety
of research projects at Stanford, incuding the DART project (automated
diagnosis of computer hardware failures) and the Intelligent Agents
project (smart interface for computer operating systems). The system
has been exported for trial use by the Hewlett-Packard Co. and the
Rand Corp.
In its initial state, MRS uses a "propositional" representation
for storing information. The representation is fully indexed and has
a flexible context mechanism. Before carrying out any operation, the
system uses depth-first backward chaining at the meta-level to figure
out how to carry out the operation. Initially, application-level
deductions also use depth-first backward chaining.
In addition to the core system, several "plug-in" modules that
substantially increase the capability of MRS have been built. The
agenda module provides the system with the ability to do breadth-first
and best-first searches in addition to the default depth-first search.
The property list module allows the user to store facts in a
frame-like property list representation instead of the propositional
representation. The demon module allows the user to write general
"if-needed" and "if-removed" methods.
Future Work
Our primary effort in the continued development of MRS is being
devoted to the costruction of useful new "plug-in" modules and a few
extensions to the inference capabilities. The issues of primary concern
at this point include an implementation of default reasoning and reasoning
with equality.
At a more theoretical level, we are expanding the system's capabilities
to reason about its own structure and behavior. Specifically, we would
like to give the user the capability to specify "invariants" that the system
will automatically enforce. We would also like to implement a module that
can reason about the structure of the knowledge in particular application
areas in order to choose or design an appropriate representation.
⊗
∂ 14 Jul 1981 2254-PDT KAPLAN at SRI-AI Origins of MRS
To: csd.lenat at SU-SCORE, csd.Smith at SU-SCORE, csd.Greiner at SU-SCORE,
csd.grinberg at SU-SCORE
cc: kaplan at SRI-AI
Dear people:
I need a quick answer on the following -
For a document that has to go via net to DARPA on this Wed., I mention MRS
and note that it was developed at MIT (by Mike, I think as part of his thesis).
If this is incorrect, i.e. if he developed it here, I would appreciate it
if one of you could let me know for the sake of accuracy.
Thanks much,
Jerry
-------
---------------
∂TO KAPLAN@Sri-Ai (CC CSD.LENAT, CSD.SMITH, CSD.GRINBERG) 11:08 15-July
Everything you always wanted to know about MRS...and more
Jerry -
Nope. As part of his thesis work, Mike wrote a predicate-calculus
like representation language named DB. On coming to Stanford, he and others
(including Doug Lenat, Dave Smith Mark Stefik and myself)
began rethinking what should go into a representation language (rl);
in particular, focussing on what sorts of things
seemed wrong or incomplete about all the existing ones.
@BEGIN(Propoganda)
The basic problem was that these rls were inflexible,
and were almost impossible to extend to match new user's needs and wants.
Our conclusion was, in retrospect, both simple and obvious:
By design, a rl is built to represent facts about various domains --
eg menengitus, or mathematical equations -- in such a way that the user
can readily reason about such information.
Why not design a rl which could represent itself?
This way the user could probe about the underlying "rl interpreter"
to help understand the language;
furthermore, this transperancy could permit the user
to modify the language as he wishes, easily.
@END(Propoganda)
The first such language designed to represent such representation language
features was RLL (for Representation Language Language).
Unfortunately need forced this to be implemented too quickly, before many
important issues were resolved. This tension (build a good, usable language
with enough self-modifiability that our needs will be met; versus design and
build the ultimate language, spending as much time now as necessary to really
understand and resolve the wealth of time-consuming issues which would otherwise
plague future work) forced Mike to splinter off, and, with much help from
Dave and some heckling/assistance from yours truly, to begin work on that
pie-in-the-sky rl, MRS -- the Modifiable Representation System
(or Mike Russ Smith, or the next version after MISS, or ...).
The most modifiable aspect of this system, to date, has been its name -- which
has now evolved to stand for Multiple Representation System.
Various potentially relevant pseudo-documents include
HP-80-8 (CORLL, the system on which both RLL and MRS are built)
HPP-80-9 (basic RLL manual)
HPP-80-23 (extended RLL appendices)
HPP-80-24 (MRS introduction)
HPP-81-6 (first Multiple RS paper)
&
"Models and Metaphors" by MRG, and Doug & my "RLL - A Rep Lan Lan" papers,
in AAAI#1.
That answer your question?
Russ
∂15-Jul-81 1122 David E. Smith <CSD.SMITH at SU-SCORE> Re: Everything you always wanted to know about MRS...and more
Date: 15 Jul 1981 1121-PDT
From: David E. Smith <CSD.SMITH at SU-SCORE>
Stanford Phone: (415)497-1809
Subject: Re: Everything you always wanted to know about MRS...and more
To: RDG at SU-AI
cc: kaplan at SU-SCORE
In-Reply-To: Your message of 15-Jul-81 1108-PDT
I'd say that DB/ANALOG had considerably more impact on MRS than did RLL. -- de2
-------
∂15-Jul-81 1134 KAPLAN at SRI-AI Re: Everything you always wanted to know about MRS...and more
Date: 15 Jul 1981 1125-PDT
From: KAPLAN at SRI-AI
Subject: Re: Everything you always wanted to know about MRS...and more
To: RDG at SU-AI
cc: csd.lenat at SU-SCORE, csd.smith at SU-SCORE, csd.grinberg at SU-SCORE
In-Reply-To: Your message of 15-Jul-81 1108-PDT
Thanks for the info, I have revised and sent the draft to reflect the
correct story.
Sorry for the confusion,
Jerry
-------
[RLL Section of BES Book - Original - sent to DBL, thence to Waterman]
(ca 10 July 1981)
RLL
2.2.8.1. Motivation
Expert systems are based on the observation that many problems
(such as medical diagnosis, or legal reasoning) are very
difficult. Due to both the sheer number of the constinuent
parts (eg court cases, or known laboratory techniques),
and to the intricacies of their interactions,
computers seem better able to cope with such tasks than humans.
So expert systems evolved, to help (human) domain expert manage
both the bulk and complexities associated with these chores.
Experience with such expert systems has lead to an interesting,
although usually overlooked, insight:
the programs which help design and implement
expert systems are themselves complex beasts.
Indeed, the domain of programming exhibits
the same types of complexities
that prompted computer scientists to build expert systems in the first place.
For example, one can use partial specification equally well
in any planning task, whether the domain be
designing molecular genetics experiments or constructing computer programs.
NEEDS WORK!!
2.2.8.2. Overview of RLL
This realization triggered RLL's development.
It is, first, a collection of tools which help
the KE to construct, use, and adapt an Expert System program.
In addition, it is itself a bona-fide expert system --
knowledgable in facts about programming in general, and its own subroutines
in particular.
This competency permits RLL to "understand" its internal inference procedures,
and provides the user with a tool for modifying these programs
to meet his specifications (rather than vice versa).
<<<< Begin >>>> ****** Is this needed ****** <<<< Begin >>>>
Every ES must have a "competence model" of its domain.
It is this knowledge which allows
that system to reason about the facts of its field.
(For exmple, MYCIN's "knowledge" of the facts about meningitus
is used to answer questions about the nature, cause
and effects of this disease.)
On the other hand, although MYCIN uses a backward chaining
inference engine to perform its deductions,
its "knowledge" of this process is limited to a weak "performance model"
-- MYCIN could not tell the user why it chose this particular control structure,
or indicate how exactly it works,
except by example.
While the domain of any Expert System Building program (ESBp) is
programming, few have a real "competence model" of this domain --
i.e. few have any "deep understanding" of the
programming constructs of the target programs they are building.
(EG while AGE can construct a Blackboard based reasoning system,
it cannot reason about such a system -- to answer questions about,
for example, its effeciencies; nor can it modify that BB model, to
handle, for example, a different type of rule.)
Like the other ESBps, the RLL system begins with a store of such constructs.
This class includes a non-trivial collection of types of slots, control
mechanisms, and inheritance schemes.
Each of these units is described in RLL's formalisms.
This specification is sufficiently "deep" that arbitrary ensembles
of these parts can be combined;
and it is this collection of parts which
forms the user's particular representation language.
However RLL was designed with the realization
that no single set of starting primitives could possibly satisfy
all of the users all of the time.
Hence RLL goes on to provide a number of tools,
which the user can use in constructing his own pieces --
for example, the user can create a new type of slot or inheritance procedure
by performing a simple modification to a "close" existing one.
<<<< omit this
RLL's competence model is essential at this point.
Many indirect ramifications may arise when
such a modification is performed, and the overall system must
be able to find all parts of the systems which may be affected by this change,
and update these pieces appropriately.
RLL's collection of facts about the field of programming
may be necessary ...
omit this >>>>
<<<< End >>>> ****** Is this needed ****** <<<< End >>>>
This permits it to "understand" what it is doing as it constructs the
target Expert System, using a reasoning process not unlike Tierasias's;
only more elaborate and encompassing. (Ie Tierasias had only a rudimentary
understanding of certain forms, within a small set of molds.
RLL can actually create new molds as necessary.)
RLL can create new modes of inference, with the same types of steps
a program like CASNET would use to incorporate a new
fact about a patient, or a new type of disease.
The next two subsections will indicate how RLL's flexibility aided us
in designing, building and updating the Oil Spill System we built, OSS.
Section 2.2.8.3 outlines the approach we followed in contructing OSS.
Notice that RLL allowed the specifics of the problem to guide the
nature and implementation of the final system
-- rather than force OSS into some particular formalism,
we designers were given great latitude in determining what
control structures to use, as well as the form of the data.
This permitted the system builders to make
effectively all of the important design decisions,
rather than be limited by the particular options which happened
to be included in the ESBp.
One of RLL's forte is its adaptability -- this carries over to the
programs it is used to construct.
Section 2.2.8.4, in listing RLL's major points, shows how easy
it was to modify OSS, both as we were building it,
and as we revised/upgraded it, after its "completion".
We next show some of RLL's main weaknesses,
both those inherent to this type of system, and those which
are only present in the current implementation.
The conclusion answers a few remaining question - such as RLL's historical
genesis, and how problems of efficiency are solved.
<<<<BELOW: THIS PART WAS EXCISED - it will be included in Rand report>>>>
2.2.8.3. Approach to Oil Spill Problem
We outline below the approach we followed in building OSS, a program
for handling (a subset of the problems associated with) inland
chemical spills.
Step 0: Determine what problem was to be solved.
(Note this step is unusual for KE tasks in general.
The particular task is usually fairly well defined
before the programme has even been contemplated.)
We decided OSS would concentrate on
solving the backtrack-to-source problem; but would include
a wide range of facts pertaining to this overall inland chemical spill situation.
Step 1: Decide what data should be represented.
We encoded as units facts ranging from very general statements about spills,
down to what pipe connected to which manhole in this installation.
Note that we had NOT decided yet how to represent these facts -- ie into
what set of hierarchies, and with what properties explicitly stored --
This is delayed until Step 3, after the basic control algorithm had been proposed.
(As AA texts will show, this is a good practice, as it avoids a premature
commitment to an awkward representation.
Note further that this is only possible in a system which
permits more than one structure for the data,
and more than one mode of inteference, such as RLL.)
In addition to the standard collections of individuals (eg Pipe#34), class of
such objects (eg AnyPipe, which refers to the set of all pipes) and the features
associated with such "set theoritical" objects,
we realized we would have to represent events -- general objects
which could be gradually refined. An example should help drive home this idea:
We may want to say general things about oil spilling into a body of water --
for example, that it causes a sheen.
We would prefer to place all such facts on one place,
eg the OilSpillingIntoWater unit, and know that every more specialized case,
eg oil spilling into the stream, will inherit such facts. (That is, that oil
will cause a sheen in the stream.)
So we would want the OilSpillingIntoStream unit to inherit everything
found in the more general OilSpillingIntoWater unit.
We could go on to describe
facts about OilFromPipe93SpillingIntoWOC,
in turn, can be further restricted into
MachineOilFromPipe93SpillingIntoWOCAfterOutFall93, (which can be
restricted to DayOldMachineOil#2FromPipe93'sFirstOutletSpillingIntoWOC-
AfterOutFall93onAug23.
Of course,
these units are not simply produced
arbitrarily -- only when you have something to say about such an
event will you create a gestalt to hold this information. If the fact
is general, it should go on a general event unit, which enables its
descendants to inherit these facts.
Anyway, the mechanism for handling this type of inheritance is distinct from
the more standard ElementOf or SubsetOf relations; and in RLL one can state
just what is expected of this relation precisely and explicitly.
Step 2: Decide on the Control/Inference Algorithms
To properly perform this step it is essential to analyze the characteristics
of the eventual system.
For example, the complete OSS is expected to perform a variety of different tasks
-- from determining the type of the spill to performing various
<remediation tasks>, such as notifying the authorities.
Another important characteristic of this job is the timeliness and ordering
of these tasks --
the importance of recording the name of first witness dwindles when
compared with telling him not to breathe the toxic fumes.
Hence determining the toxicity of the vapors
should be of tantamont importance,
especially when the leak might be near people.
A well structured agenda seemed ideally suited to these specifications.
(An additional plus was that
even this still immature RLL system already had this program construct.)
The agenda contains an ordered list of tasks, which are processed sequentially.
Each task is designed to performs a particular bitesize job.
For example, the goal of one task may be to determine the values
of some parameters, (e.g. the task MatType attempted to deduce
the type of material which had spilt,)
another may add other tasks to this agenda,
(for example, the task in charge of effecting the Countermeasures added
several new tasks to the agenda - one to notify the authorities, another to ...)
and a third type would print out instructions/requests to the user
(eg "go to Manhole #34 and tell me if you see oil").
Other kinds of tasks (which were not necessary for this particular domain)
could create a new concept,
or decide to rearrange the tasks on the current agenda,
in recognition of some new fact.
Executing a task meant collecting relevant rules, then ordering and firing
this list in sequence.
There are many types of rules, each charged with (attempting to) achieve a
different type of goal.
(In this sense they are similar to tasks, only in a smaller scale.)
Some rules employ a known technique (algorithm) to evaluate
the value of some attribute.
(For example, determining the toxicity of a given material by looking
it up in a table.)
Others may decide to add additional rules to this rule-set,
or propose adding a particular new task to the agenda.
Still others may suggest that the current task (in which this rules occurs)
be suspended, to await necessary new data.
(Note the flow of command is quite structured.
Each rule, task or agenda* can only effect its immediate surroundings.
More global changes are performing to sending messages to its overlord,
proposing this alteration.)
* Footnote: RLL (EURISKO) is capable of dealing with several agendae --
swapping among them as need arises.
This facility was one of many RLL features which were not needed
for this job.
We will discuss below how the rules themselves will be represented,
along with the benefits of this format.
<<<<ABOVE: THIS PART WAS EXCISED - it will be included in Rand report>>>>
Step 3: Decide how to represent the facts/procedures/rules...
3a) Once the overall inference mechanism has been determined
3b) Decide how to represent the control mechanism
Before we can describe the sort of decisions which are made at this
point, a brief digression is necessary -- to explain RLL's basic philosophy,
and how this permits us to decide on the representation to use.
(We'll tell you when the digression is over.)
RLL is based on the "To every thing, a unit" philosophy.
This uniform representation system extends beyond just encoding the
domain knowledge -- here facts about types of oil and connectivity of pipes.
Units are used to store facts (as well as the executable code) associated
with the representation itself -- such as the descriptions for each type of
slot, or the procedure used to process a given task.
*--------*--------*--------*--------*
M6-3
Isa: (AnyManhole)
FeedsInto: (M6-2)
M6-2
Isa: (AnyManhole)
FeedsFrom: (M6-3)
AnyManhole
Examples: (M6-2, M6-3, ...)
Description: This represents the class of all manholes.
*--------*--------*--------*--------*
RLL is (unfortunately) committed to using a semantic net based representation,
based on gesalts called "units",
whose attributes are defined with a set of property-value pairs*)
[* footnote: these properties are called Slots, for historical reasons.]
Within this minor constraint, RLL does provide great flexibility.
We show below that the information relevant to each type of slot is stored in
a unit.
The unit below shows that:
The value of x:FeedsInto must be a list of manholes, the only x for which
x:FeedsInto is defined is a manhole, and that if x:FeedsInto = y, then
y:FeedsFrom = x (i.e. FeedsInto:Inverse = FeedsFrom).
*--------*--------*--------*--------*
FeedsInto
Isa: (AnySlot)
Description: This slot maps from manholes to manholes.
Inverse: FeedsFrom
HighLevelDefn: (Composition OtherEnd ConnectedPipes)
Domain: Unit representing a manhole.
Format: SingleElements
Datatype: Unit repesenting a manhole.
ToCompute: (λ (u) [Find the pipe, P, to which this manhole connects.
See which pipe, p', to which this P is connected.
Return the manhole m, which is connected to
pipe p'.]
Note - the ToCompute of a slot indicates how to deduce its value -- i.e.
S:ToCompute is a function, F, whose value, (F u), is the value to fill
u:S.
*--------*--------*--------*--------*
It is important to realize that those facts shown above are not JUST a description
of the FeedsInto type of slot -- it really is used to define this slot.
If any of those slots were ever changed, the way this slot behaves would
be affected. For example, declaring FeedsInto:Format is a SetOfElements would
cause RLL to redefine each FeedsInto:ToCompute to return a singleton list
rather than a single atom (corresponding to that manhole,)
and to (retroactively) fix up each value of u:FeedsInto.
[If that value was empty, it would remain empty. Otherwise the single value
v would be changed into the list (v).]
Similarly, each data structure -- each rule, task, and agenda --
is stored as a unit.
This permits (facilitates) the data to dynamically altered during
the course of the computation, or through user input.
(IE one can use the same procedures to add in a new rule that are used
to add a new pipe, or new type of slot.)
Even the procedures of this system
-- the parts of the control structure outlined above --
are encoded in units.
As with parts of the repesentation, these facts are actually used as the
system is run.
For brevity, we will only address one of these chunks -- the rules.
Each rule has a number of obvious attributes.
First, the rule has to store the actual code which is to be executed.
The user is spared the task of enterring the
actual LISP expression to be run;
instead he provides a higher level specification of what this rule
is to do, and RLL "expands" this definition into that code.
There are several major advantages to
providing both high and low forms of a rule specification.
In addition to facilitating the creation of a new rules,
this higher level makes the nature of the rule easier to understand
and reason about, for both the user and RLL itself.
*--------*--------*--------*--------*
Rule#332
Isa: (AnyRule)
Description: Tell the user to hold his breath if the chemical is toxic.
IfPotentallyRelevant: (APPLY Toxic Chemical)
IfTrulyRelevant: (APPLY NearbyUser ChemicalHasSeepedTo)
ThenTellUser: "Do not breath this chemical!!"
ThenAddToAgenda: EmergencyProcedures
Priority: High
OnTask: ImminentDanger
ImminentDanger
Description: This task tries to find if the current situation is
dangerous; and if so, suggest solutions/fixes/alternatives.
Isa: (AnyTask)
RuleList: (Rule#332, ...)
EmergencyProcedures
Description: This task is called iff the current situation is dangerous;
and issues many quick-and-dirty orders.
Isa: (AnyTask)
RuleList: (Rule#981, ...)
-Note the rule above is what the user would type,
and not the actual running code which RLL would compute as needed.
*--------*--------*--------*--------*
Notice the code for this rule is scattered about, stored in several distinct
slots.
This permits different parts to be executed independently --
for example, allowing the quick IfPotentially check to run to all of wide
class of rules; and then running the more expensive IfTrulyRelevant part
only on that small subset which passed.
The THEN parts are also split up. Once the IF-parts have all passed, each
of those is, in sequence run.
Of course what we described above was the way the rule was evaluator, "by default"
- read that, unless the user has something else in mind.
Recall any user can readily modify that rule-evaluating procedure as well.
So, for example, the user may decide instead to execute the code implied by
the IfWorkingOnTask slot of a rule, or IfTodayIs, or any other set of slots.
(rather than the current IfPotentiallyRelevant and IfTrulyRelevant slots
now used.) Or he may decide to compose a single IF-Part, which ANDs together
all of these, and runs these at once. Similarly he may want the THEN parts
executed in a different order; or may have decided to only run those THEN parts
for which he has sufficient resources.
Note that this could not be done if each rule was simply a single piece
of compiled code.
We claimed above that it was easy to change the rule interpreter.
This is because that block of code is itself an RLL unit.
Like the rules, it is decomposed into nice sized chunks, which can
be independently modified.
One such hook is a list of slotnames which constitute
the IF part of a rule, together with a description of when that code should
be executed. Details of this, and other specifications, can be found in [Greiner].
Before leaving this rule description, there are several other
"declarative" facts stored in each rule.
One important slot is the average CPU time this rule has spent, for executing
its IF parts and THEN parts, respectively. This can be used for various
meta-reasoning tasks -- such as deciding whether to even consider this rule
in the future (ie did its bang justify its bucks).
Another field is the rule's author - be in human or another rule.
This can help decide who to credit/blame for good/bad rules; and this data
can help the overall system to improve its performance by relying more and more
on capable (that is, successful) rule writers.
Finally, the user himself can store any other type of information he wants --
these are just things which we feel may be useful types of statistics.
Similar mechanisms exist for processing agendae, or tasks, or other control
regimes. (For example a black board architecture, for other types of tasks.)
There are corresponding varieties of data structures - ways of extending tasks,
for instance.
Of course various inference schemes - most importantly an inheritance hierarchy -
is used to simplify data entry. A new rule structure can be entered by
copying the existing prototype, and changing those entries which are inappropriate.
Most properties are simply inherited from more general ideas -- here from
RLL's facts about rules in general. (In fact, for pedagogic reasons, we might
not even tell the novice user about RLL's extendability; or at least not until
he begins to complain about how awkward it is to encode this or that fact.
Until that time, he need never know anything more that a "behaviour description"
of the rule interpreter -- which is all he would ever know about the corresponding
evaluator in most other ESs.)
*-*-*-* Back to the plot *-*-*-*
The above description of rules, etc., was only to illustrate the type of decisions
one can make at this level. Here one can determine what sorts of executable slots
a rule can have, and what such slots "mean" -- that is, when that code should
be executed.
This is a further specification of the underlying type of algorithm
(here an Ordered Agenda Execution,) and is done as a seperate step, after
the overall idea had been determined.
Step 4: Run the system, and modify what has to be modified.
While (4a) "Test the neo-natal system" is standard to ESBps,
(4b) "Change those parts which should be changed" is not.
In RLL, all of the executable code is made explicit, and the user
is permitted to modify it to suit his design.
We saw in Step 3 some of tools RLL provides for such adaptations --
a high level specification language, and appropriate chunking of the knowledge.
There it was used for construction of parts -- but it can also be exploited
for retro-actively modifying existing parts.
As we saw, RLL's structure makes
changing the code as easy as altering any domain data
-- as the "program" used to test a rule's pre-condition is in the same format
as data about Oil#31, or any other bit of data used.
There are many levels of modifications permitted to data stored in RLL.
The simplest type of alteration pertains to domain data -- deciding that
Pipe#406 really joined Pipe#317, rather than Pipe#316 as you had thought.
This sort of fix could be performed in any ES.
But now suppose you realized that pipes could really join many pipes, rather
than just one. This would be difficult to say in many languages --
indeed the only solution in most might require throwing away that Connected
link and defining a totally new ConnectedS link. Even then all of the existing
data would have to be transfered, regrettably by hand.
Not so in RLL. As the example given above shows, this could be done automatically.
The actual control mechanism could be altered as well. In the initial simple
OSS system we simply pre-assigned a set of rules to each task.
Another approach would be to require each task to first gather those rules
it might need, and then fire those. This required changing the basic task
processor, by simply putting in that "initialization" proceudure.
(Fortunately this was simply adding in a pre-existing known routine.)
Nonetheless, this fix was quite easy to make.
The initial implementation wasn't worried about time or space problems.
Each task ran until it thought it was done, and then the task which was
next in importance started up. We then decided this was sub-optimal -- as
some tasks might become gradually less important, to where some sub-part of
another task would be more relevant.
So we changed the task-interpreter again, to suspend tasks after some length
of time. Another fix could (but wasn't made) in the Agenda-processor to
only consider tasks which could be achieved in x units of time.
(This too would be easy - by adjusting the weight function, used to evaluator
the worth of each task. The ordering of the agenda is determined by this measure.)
There were several other things which we considered but decided not to change:
One was to use more general types of rules -- where each rule could dictate
how to fire it, in each given situation -- eg when gathering rules, or testing
preconditions, or .... This would permit IfThenElse types of rules,
or even "rules" which were simply a procedure
-- perhaps a call to a Fortran program.
2.2.8.4. RLL's Strengths and Weaknesses
WINS
Throughout this report we have pushed RLL's strengths -- basically these
all derive from RLL's "competence model" of programming in general,
and of the data structures and algorithms it uses in particular.
Not mentioned was its capability to ignore InterLisp's 256K storage
maximum, using a demand paging algorithm [CORLL], and its basic Lisp support --
providing advantages like spelling correction, and inline editors.
From the above descriptions imply that RLL is actually "executing" high level
specifications of various control algorithms.
Were this true, RLL would have sacraficed any hope for speed and
(time-)efficiency for the sake of flexibility.
That is NOT the case. While RLL does preserve these high level descriptions
definitions, it ALSO stores what these forms "compile" into -- and it
is that latter body of code which is actually run.
Much of RLL boot-strapping code is devoted to preserving such interrelationships --
so that any change to a high level form marks the (formerly-)corresponding
executable code as invalid. On demand (that is, the next time that code
is needed,) RLL will expand that new high level definition into runnable
code; and store these low level forms so they will accessed speedily
next time the code is needed.
Returning now to the question of efficiency, we see that RLL's code
can be arbitrarily fast.
Rather than "interpret" the high level descriptions, RLL first "compiles"
these into efficient forms, and runs this faster code.
This costs only a constant overhead -- for the one time charge of
expanding that terse description. From there on the code can be
arbitrarily efficient.
Basically RLL has paid for its flexibility in terms of space -- to maintain
the different versions of the code -- and not in time.
More details on how these multiple versions are maintained, used and cached
can be found in [CogEco].
LOSSES
RLL's biggest problem, at this stage of its development, is its immaturity.
By design, it will continuously incorporate new facts about control structures,
forms of representation and modes of inheritance.
However, OSS was built way too early in this ongoing design process.
For example, RLL had never encountered a Solvable Problem before --
all of its previous work had been directed towards AM-like searches --
things which never terminal with a final verdict (ie RLL knew about tasks
like "Find examples of primes", but not about things like "What is the source
of the spill").
Another big weakness, which also stemmed from its youth, was its lack of
a user front end. A trivial example involves the way we were forced to
enter the code -- everything was in a LISPy (GetValue 'Material
'Name), rather than a nicer "Material's name".
At a deeper level, RLL did not yet have any notion of context --
this forced us designers to explicitly type (continuing the above example)
"Material name" rather than the (sufficient) "name".
A good front end could have aided in the design of this system, by suggesting
appropriate data structures and algorithms as we went. This too was missing.
The final major fault seems almost paradoxical:
it was RLL's total adaptability.
Too much freedom, we found, forced us to spend considerable time
deciding which really was the best.
This time, of course, was not ill-spent; the final OSS is certainly
better than any comparable system which forced out hand at each step,
molding out final code to match its limited set of components.
However, any such external constaints would have
narrowed down our search, and helped us finish the system in the
four days we were allotted.
Once again this type of problem could have been alleviated in a more
mature system, which included a competent front end which would have
served as "gentle guide" during this building process.
2.2.8.5. Conclusion
We will conclude win a perspective of RLL -- in terms of its past, its
current status, and our long term plans.
A year ago, RLL began as a two week project to build a representation language on
which the EURISKO system would be built.
We soon realized many non-trivial research issues had to be addressed before
such a general, "self-encoding" language could be constructed.
(We eventually abandoned the quest for this ultimate language, satisfying
ourselves with the generality which was possible within a limited set of
constraints. The more theoritical aspects of this rll work was taken up
by other members of the HPP community; and their next step is described in
[MRS].)
The current system plays a necessary boot-strapping role -- certain parts
of the system must be present, as these are used to fill in other parts.
(For example, the code which is used to expand high level definitions must
be present -- or at least enough of it to generate the rest of it.)
The initial control mechanism was the one needed for the EURISKO work --
which was an Agenda structure. OSS used a minor variant of this system.
In the long run we will actually build RLL into the MRS system -- viewing
each of the seperate decomposable parts of this systems as an MRS module,
which can be individually or collectively plugged in (ie activated).
Using MRS as a Lingua Franca, RLL will be able to absorb a large corpus
of knowledge and examples from a multitude of users -- the MRS community.
Each of these other modules will hold facts about a particular domain, or
part of that domain -- eg Medical tutoring, VLSI design, or planning experiments
in the field of Genetics.
For its part,
These RLL-based MRS modules will store facts about certain types of representations,
together with their major applications.
Important in this list will be expertise about expertise.
It is this knowledge which will enable RLL to fashion new ESs with greater
efficient and accuracy.
BOTTOM LINE
While other ESBp systems have proven expedient for tackling particular problems
in particular domains, we feel such systems will always be limited
in the scope of problems they can solve.
We feel this problem is intrinsic to such programs, at least until
they, like the human programmers they are trying to emulate,
are capable of a crude understanding the code they are composing at something
more than the superficial level now attains.
RLL was written with the goal of attaining this necessary
undertanding.
[My version, after fix up (after Don, after DBL,from me)]
∂ Monday, 6 Jul 1981 15:33-PDT Re: tools chap
To: CSD.LENAT at SU-SCORE
Cc: don at RAND-UNIX
In-reply-to: Your message of 25 Jun 1981 1502-PDT.
From: don at RAND-UNIX
Doug: I reorganized your section for you -- the material I pulled out will
go into the Rand Report. Naturally, you will have to modify the content of
the chapter yourself. It still needs a bit of work to smooth it out and
change the emphasis from a description of the SPILL program to a
description of RLL using the SPILL problem to illustrate important points.
I need your revised chapter as soon as possible (yesterday) so I can send
the publishers we are considering the draft of the book they have been so
patiently awaiting. We will not send them anything on the metacognition
section since (I assume) it won't be ready for some time.
I put a copy of the tools chapter draft into the mail for you today. It
may help to see how the other people have organized their sections of
the chapter.
Regards,
Don
------------------------------------
(16 July 1981)
2.4.1 RLL
Expert systems (ESs) are based on the observation that many problems
(such as medical diagnosis, or legal reasoning) are very
difficult. Due to both the sheer number of the constinuent
parts (eg court cases, or known laboratory techniques),
and to the intricacies of their interactions,
computers seem better able to cope with such tasks than humans.
So expert systems evolved, to help (human) domain expert manage
both the bulk and complexities associated with these chores.
Experience with such expert systems has lead to an interesting,
although usually overlooked, insight:
the programs which help design and implement
expert systems are themselves complex beasts.
Indeed, the domain of programming exhibits
the same types of complexities
that prompted computer scientists to build expert systems in the first place.
For example, one can use partial specification equally well
in any planning task, whether the domain be
designing molecular genetics experiments or constructing computer programs.
This realization triggered RLL's development.
It is, first, a collection of tools which help
the KE to construct, use, and adapt an Expert System program.
In addition, it is itself a bona-fide expert system --
knowledgable in facts about programming in general, and its own subroutines
in particular.
This competency permits RLL to "understand" its internal inference procedures,
and provides the user with a tool for modifying these programs
to meet his specifications (rather than vice versa).
This section will quickly overview this RLL system, taking examples
from our experience coding up OSS -- the Oil Spill System.
As a secondary goal (in addition to describing RLL,) we hope to
express our conviction that (i) a self-encoded system -- one which can
begin to "understand" its own operations to where it can assist in
performing such modifications --
is immensely worthwhile, especially in the long run;
and (ii) that the price of this capability is really not that great.
!2.4.1.1 Overview of RLL
Every ES must have some "competence" of its domain.
It is this knowledge which allows
that system to reason about the facts of its field.
(For example, MYCIN's "knowledge" of the facts about meningitus
is used to diagnose patients who have this disease, and
to propose medications.)
On the other hand, although MYCIN uses a backward chaining
inference engine to perform its deductions,
its "knowledge" of this process is limited to a weak "performance model"
-- MYCIN could not tell the user why it chose this particular control structure,
or indicate how exactly it works,
(except by example).
<<<Doug - this paragraph must be changed for political reasons>>>
While the domain of any Expert System Building program (ESBp) is
programming, few have a real "competence model" of this domain --
i.e. few have any "deep understanding" of the
programming constructs of the target programs they are building.
(EG while AGE can construct a Blackboard based reasoning system,
it cannot reason about such a system.
For example, it cannot answer questions about its efficiencies;
nor can it modify its basic Blackboard model to handle,
for example, a different type of rule.)
Like the other ESBps, the RLL system begins with a store of such constructs.
This class includes a non-trivial collection of types of slots,
(such as Isa or RangeType,)
control mechanisms,
(eg Backward chainers and agenda processes,)
and inheritance schemes
(for example, the ExampleOf relation).
Each of these units is described in RLL's formalisms.
This specification is sufficiently "deep" that arbitrary ensembles
of these parts can be combined;
and it is this collection of parts which
forms the particular representation language KE will use.
However RLL was designed with the realization
that no single set of starting primitives could possibly satisfy
all of the users all of the time.
RLL therefore include provide a number of tools,
which the user can use in constructing his own pieces.
For example, the user can easily create a new type of slot
or inheritance procedure.
(One standard "creation" method involves copying
a "close" existing chunk, then modifying that copy.)
RLL's competence model of programming is essential at this point.
There are many indirect ramifications which arise when,
say, a new laboratory technique is added to Molgen's data base;
similarly there are a host of actions which must be taken
when some part of the underlying representation is changed.
Just as Molgen's code is responsible for propogating the effects of this
new data, so the overall RLL system will
find the parts of the systems which may be affected by this change,
and update these pieces appropriately.
RLL allows the specifics of a problem to guide the
nature and implementation of the user's final ES
-- rather than force the system into some particular formalism.
The KEs are given great latitude in determining what
control structures to use, as well as the form of the data.
This permits the system builders to make
effectively all of the important design decisions,
rather than be limited by the particular options which happened
to be included in the ESBp.
So much for the overview and motivation.
The rest of this RLL section attempts to flesh out this skeletal description.
Subsection 2.4.1.2 explains how facts are represented in RLL ,
and shows how this structure is adequate to handle knowledge
about both the particular domain (eg Oil Spills) and RLL internals themselves
(eg facts about slots or control mechanisms).
This section includes a concrete example, using RLL's management of rules
to show first how the facts are stored, and then
how various type of
modifications can be done -- ie how RLL has attained this degree of flexibility.
Section 2.4.1.3 describes the control structure used for this partcular OSS
application, in a fair amount of detail.
This sections also explains how RLL can simultaneously be explicit and perspecious,
and yet maintain a high level of efficiency.
The last two concluding sections describe first, how RLL fits into the world,
and then overviews what still has to be done.
!2.4.1.2 Knowledge Representation in RLL
RLL is based on the "To every thing, a unit" philosophy.
This uniform representation system extends beyond just encoding the
domain knowledge -- here facts about types of oil and connectivity of pipes.
Units are used to store facts (as well as the executable code) associated
with the representation itself -- such as the descriptions for each type of
slot, or the procedure used to process a given task.
*--------*--------*--------*--------*
M6-3
Isa: (AnyManhole)
FeedsInto: (M6-2)
M6-2
Isa: (AnyManhole)
FeedsFrom: (M6-3)
AnyManhole
Isa: (AnyClassOfObjects)
Examples: (M6-2, M6-3, ...)
Description: This represents the class of all manholes.
*--------*--------*--------*--------*
RLL is (unfortunately) committed to using a semantic net based representation,
based on gesalts called "units",
whose attributes are defined with a set of property-value pairs*)
We will show below the great flexibility RLL does provide,
within this minor constraint.
[* footnote: these properties are called Slots, for historical reasons.
We use the notation Unit:Slot to refer to the value of the Slot slot of
the unit Unit.]
The above units refer to specific objects which exist in the real world --
eg M6-3 represents manhole #2 on ? #6 --
or classes of such objects --
as AnyManhole encodes facts about the set of all manholes.
Other types of units which refer to things like events, which,
unlike individuals, can have varying degrees of generality.
An example should help illustrate this point:
We may want to say general things about oil spilling into a body of water --
eg, that it causes a sheen.
Ideally all such facts should be stored in one place,
say the OilSpillingIntoWater unit,
in such a manner that every more specialized case,
will inherit these facts.
Ie we would expect RLL to conclude
that oil spilling into a stream will cause a sheen in that stream
once it knows that
OilSpillingIntoStream is a specialization of
OilSpillingIntoWater.
We could go on to describe
facts about OilFromPipe93SpillingIntoWOC,
in turn, can be further restricted into
MachineOilFromPipe93SpillingIntoWOCAfterOutFall93, (which can be
restricted to DayOldMachineOil#2FromPipe93'sFirstOutletSpillingIntoWOC-
AfterOutFall93onAug23.)
It is important to realize that these units are not simply produced
arbitrarily --
such event units are created only when there is some
pertanent fact to preserve about the event.
When the fact
is general, it should go on a general event unit, which enables its
descendants to inherit these facts.
Anyway, the mechanism for handling this type of inheritance is distinct from
the more standard ElementOf or SubsetOf relations; and should be treated as such.
RLL insures this seperation by allocating
different units to store facts about each type of inheritance.
Various properties of these inheritance-defining units
indicate how to initialize a new unit
(as stating that Pipe#33 is an Example of AnyPipe should be handled quite
differently from the statement that OilSpillingIntoStream is a
Specialization of OilSpillingIntoWater), or how the values of some slot
may be altered, to maintain this particular inheritance relation.
(eg the SubstanceSpilt of any Specialization, S, of OilSpillingIntoWater must be
some refinement of Oil, whereas S:TimeOfSpill can be arbitrary.
Analogously Pipe#33 can have slots like Length or TimeOfCreation, but not
things like Father or RangeType.)
Exactly how such data is encoded is far too detailed (and irrelevant) for
this report; the important fact is that such facts can be
stated precisely and explicitly in RLL.
Furthermore, such facts can be altered by the user, if his task demands it.
Indeed, the user can even create new "representational pieces":
As none of RLL's prior tasks had needed this Specialization inheritance,
our starting system did not have this particular feature.
We therefore had to design and build
this totally new mechanism, and incorporate it into RLL,
an all but impossible for most ESBps.
Thanks to tools RLL provided, this chore was quite easy.
Note that this feature is now a part of RLL --
subsequent users can now use this type of inheritance,
as easily as any of the other ones RLL "always" provided.
[*fnnote: Returning to a point made in the introduction,
we envision RLL will be constantly growing -- largely through additions
provided by its users. Eventually this growth, we hope, will slow down;
once a "critical mass" of useful features have been built. Needless to say,
this has not yet occurred.]
Slots are another type of representational piece.
As with inheritance modes,
the information relevant to each type of slot is stored in a unit.
The unit below shows that:
The value of x:FeedsInto must be a list of manholes, the only x for which
x:FeedsInto is defined is a manhole, and that if x:FeedsInto = y, then
y:FeedsFrom = x (i.e. FeedsInto:Inverse = FeedsFrom).
*--------*--------*--------*--------*
FeedsInto
Isa: (AnySlot)
Description: This slot maps from manholes to manholes.
Inverse: FeedsFrom
HighLevelDefn: (Composition OtherEnd ConnectedPipes)
Domain: Unit representing a manhole.
Format: SingleElements
Datatype: Unit representing a manhole.
ToCompute: (λ (u) [Find the pipe, P, to which this manhole connects.
See which pipe, p', to which this P is connected.
Return the manhole m, which is connected to
pipe p'.]
Note - the ToCompute of a slot indicates how to deduce its value -- i.e.
S:ToCompute is a function, F, whose value, (F u), is the value to fill
u:S.
*--------*--------*--------*--------*
It is important to realize that those facts shown above are not JUST a description
of the FeedsInto type of slot -- it really is used to define this slot.
If any of those slots were ever changed, the way this slot behaves would
be affected. For example, resetting FeedsInto:Format to be SetOfElements
(rather than SingleElement) would
cause RLL to redefine FeedsInto:ToCompute to return a singleton list
rather than a single atom (corresponding to that manhole,)
and to (retroactively) fix up each value of u:FeedsInto.
[If that value was empty, it would remain empty. Otherwise the single value
v would be changed into the list (v).]
Similarly, each data structure -- each rule, task, and agenda --
is stored as a unit.
This permits the data to dynamically altered during
the course of the computation, or through user input.
(IE one uses the same procedures to add in a new unit, independent
of whether that unit represents a new rule,
a new pipe, or new type of slot.)
Even the procedures of this system are encoded in units --
including especially the parts of the control structure outlined below.
As with parts of the repesentation, these facts are actually used as the
system is run.
For brevity, we will address details of only one of these chunks -- the rules.
Section 2.4.1.?, which overviews the contol structure actually used,
will then sketch the other parts of the system's control,
emphasizing the advantages which come from "unitizing" these parts.
!2.4.1.2.1 Example - How RLL Encodes Rules
Each rule has a number of obvious attributes.
The primary facet of each rule is the actual code which is to be executed.
RLL spares the user the arduous task of enterring the
actual LISP expression to be run;
instead the user can type a more laconic high-level specification
of what this rule is to do.
RLL then "expands" this definition into that executable code.
(This is done in a very general, RLL-ish manner,
using facts stored in the name of the slot.
Hence it is the unit associated with the ThenTellUser slot which "knows" to
expand a message, like
("Do not breath this chemical, " Chemical "!!"
" It is " (Toxicity Chemical) ".")
into code which prints it when the user is present --
(PROGN (WriteToUser "Do not breath this chemical, " (GetVal Chemical) "!!")
(WriteToUser " It is " (GetVal (Toxicity Chemical)) "."))
)
*--------*--------*--------*--------*
Rule#332
Isa: (AnyRule)
Description: Tell the user to hold his breath if the chemical is toxic.
IfPotentallyRelevant: (APPLY ToxicP Chemical)
IfTrulyRelevant: (APPLY NearbyUser ChemicalHasSeepedTo)
ThenTellUser: ("Do not breath this chemical, " Chemical "!!"
" It is " (Toxicity Chemical) ".")
ThenAddToAgenda: EmergencyProcedures
Priority: High
OnTask: ImminentDanger
ImminentDanger
Description: This task tries to find if the current situation is
dangerous; and if so, suggest solutions/fixes/alternatives.
Isa: (AnyTask)
RuleList: (Rule#332, ...)
EmergencyProcedures
Description: This task is called iff the current situation is dangerous;
and issues many quick-and-dirty orders.
Isa: (AnyTask)
RuleList: (Rule#981, ...)
- Note the rule above is what the user would type.
RLL would use this to compute the actual to-be-run code, as it was needed.
*--------*--------*--------*--------*
There are several major advantages to
providing both high and low forms of a rule specification.
In addition to facilitating the creation of a new rules,
this higher level makes the nature of the rule easier to understand
and reason about, for both the user and RLL itself. [fnnote *]
[*footnote:
RLL is able to use different versions of the
definition of the procedure or slot for different type of tasks,
in much the same manner that InterLisp handles both compiled and interpreted
forms of each function.
When a user wishes to examine or edit a function, IL pulls in that function's
source listing, rather than force the user to peruse LAP code.
However it is that low-level LAP code which IL actually runs.
Similarly when someone wants to examine a rule,
(ie estimate how long it will take, or determine what sorts of things this
execution will affect,)
the rule's concise "declarative" form of the specification is offered.
This, of course, is NOT the form which is actually run.
The much-less-perspicious expanded form is used for this purpose.
This also represents a sizable savings of run-time speed.
Section 2.4.1.?.3 addresses this, and related, issues.]
The example above shows how the specifications for this rule is scattered about,
stored in several distinct slots.
This permits different parts to be executed independently --
for example, allowing the quick IfPotentially check to run to all of wide
class of rules; and then running the more expensive IfTrulyRelevant part
only on that small subset which passed.
The THEN parts are also split up.
In common practice, once the IF-parts have all passed, each
of the THEN parts is run, in the appropriate order.
The description above is
the way a rule is evaluated "by default" --
that is, unless the user has something else in mind.
Recall any user can readily modify that rule-evaluating procedure as well.
So, for example, the user may decide instead to execute the code stored
on the IfWorkingOnTask slot of a rule, or IfTodayIs, or any other set of slots.
rather than the current IfPotentiallyRelevant and IfTrulyRelevant slots
now used.
Or he may decide to compose a single Total-IF-Part, which ANDs together
all of these, and runs these at once. Similarly he may want the THEN parts
executed in a different order; or may have decided to only run those THEN parts
for which he has sufficient resources.
Note that this could not be done if each rule was simply a single piece
of compiled code.
We claimed above that it was easy to change the rule interpreter.
This is because that block of code is itself an RLL unit.
Like the rules, it is decomposed into nice sized chunks, which can
be independently modified.
One such hook is a list of slotnames which constitute
the IF part of a rule, together with a description of when that code should
be executed.
We will return to this point in the next section, which discusses the basic
control structure.
*--------*--------*--------*--------*
StandardRuleInterpreter
Isa: (AnyRuleInterpreter)
Description: This is the standard procedure used to interpret a given
rule. It first executes the AND-junction of the rule's
If-Parts. If the result is nonNIL, it executes all of
rule's Then-Parts.
HighLevelDefn: (IF (AND-Junction ProcessPart IfParts)
(AND-Junction ProcessPart ThenParts))
UsedByRules: (Rule#3 Rule#5 ...)
IfParts
Isa: (AnySlot)
Description: The value of this slot is the list of slots of the unit
(here a rule) which descend from the class, AnyIfPart.
These are ordered by the value of their respective
OrderForRuleParts.
HighLevelDefn: (PutInOrder (Subsetting MySlots
(ValueIncludes Isa AnyIfPart))
OrderForRuleParts)
MakesSenseFor: Rules
Datatype: Slots
Format: OrderedSetOfElements
Simplified version of the Standard Rule Interpreter.
Much of its code is "hidden" in the parts of the HighLevelDefn -- eg
IF, AND-Junction, ... Of course, these too are units, and are visible to the
interested user.
(The IfParts unit is shown, to dissuade those who do not believe this claim.)
*--------*--------*--------*--------*
Before leaving this rule description, there are several other
"declarative" facts which might be stored in each rule.
One important slot is the average CPU time this rule has spent, for executing
its IF parts and THEN parts, respectively. This can be used for various
meta-level reasoning tasks
-- such as deciding whether to even consider this rule
in the future (ie did its bang justify its bucks).
Another field is the rule's author - be in human or another rule.
This can help decide who to credit/blame for good/bad rules; and this data
can help the overall system to improve its performance by relying more and more
on capable (that is, successful) rule writers.
Finally, the user himself can store any other type of information he wants --
these are just things which we feel may be useful types of statistics.
Of course various inference schemes -- most importantly an inheritance hierarchy
-- are used to simplify data entry.
A new rule can be entered by merely copying that existing prototype,
and changing only those entries which are inappropriate.
Hence the bulk of the properties are simply inherited from more general ideas
-- here from RLL's facts about rules in general. *
[Fnnote*:
In fact, for pedagogic reasons, we might
tell the novice user only about a small subset of the slots he actually
might be able to change -- and let him believe that these are the only
things he can affect.
He would only be about this dimension of RLL's extendability
when
he begins to complain about how awkward it is to encode this or that fact,
or wonders why he can't seem to capture some particular type of idea.
Until that time, for example,
he would have nothing more that a "behaviour description"
of the rule interpreter
-- which is all he would ever know about the corresponding
evaluator in most other ESs.]
The above description of rules illustrates the degree of flexibility
available to the user at the designing stage.
The current RLL includes many rule interpreters which we, the RLL designers,
felt were appropriate and useful.
It is important to realize, however, that the eventual user is not limited
to only these.
Not only is he free to design his own interpreters,
but RLL aids in this mission, by providing tools which facilitate
constructing such interpreters.
Indeed, as these tools are represented in RLL as well, the user can even
construct his own building aids, if he feels the need.
There are similar mechanisms for implementing the processes used for
"running" agendae, or tasks, or other control regimes.
(For example a black board architecture, for other types of tasks.)
Corresponding to each such process is the data structure to which
it applies; and RLL includes means for extending or adapting those as well
-- ways of extending tasks, for instance.
This section tried to demonstrate how useful RLL's competence
in this programming domain
is when designing and building a new expert system.
The next subsection shows another application of this facility --
when the user wishes to modify his existing ES.
Here the user has the option of changing his mind later,
and know that RLL will modify not only the code,
but perform the retroactive updates to his data required to keep code and data
in synch.
!2.4.1.2.2 RLL's Modifiability
Different system have different conventions defining what part of the running
system is changable, and which is, to all but the most sophisticated user,
untouchable. By design even casual users can enter, change or delete
"domain data" -- facts, in this case, about the connectivity of pipes,
or the precise placements of various buildings.
(Eg if the user later realizes that
Pipe#406 really joined Pipe#317, rather than Pipe#316 as you had thought.)
In many representations systems,
the user can addres and modify generic objects as well --
for example, respecify which features are well-defined for types of roads,
or redraw the taxonomical information about types of oil.
In addition to these, some languages
permit the user to define totally new types of
relations -- in the form of new slots for our RLL language.
(For example, the FeedsInto slot which was handily defined as the
Composition of the OtherEnd and the ConnectedPipes slots.)
These definitions can be used to redefine the "meaning" of a slot as
well as initiate one.
Suppose you realized that pipes could really join many pipes, rather
than just one. This would be difficult to say in many languages --
indeed the only solution in most might require throwing away that FeedsInto
link and defining a totally new FeedsIntoS link.
Even then all of the existing
data would have to be transfered, regrettably by hand.
In RLL, on the other hand, all of the executable code is made explicit,
and the user is permitted to modify it to suit his design.
As section ? pointed out, RLL provides various tools for such adaptations --
for example, the high level specification language for functions,
and the use of appropriately chunking the knowledge.
(These are the same things which proved so useful for constructing of parts
-- but it is also be exploited for retro-actively modifying existing parts.)
RLL's uniform representation of facts makes
changing the code as easy as altering any domain data
-- as the facts which specifies a slot's arity is in the same format
as data about Oil#31, or any other domain or representation fact.
Furthermore, RLL's "understanding" of things like SingleElement and SetOfElements
allows it to do all the appropriate fixes, automatically.
RLL extends this modifiability to include the control structure as well.
This permits the user to
construct his own form of control, as he needs it.
The next section outlines the contol structure we found useful for this
particular Oil Spill task. We wish to emphasize, again, that this Agenda
mechanism is but one of several control structures which will appear in the
mature RLL product -- and that the user could have designed his own from
smaller pieces supplied by RLL, using tools present in RLL.
!2.4.1.3 Control
The decision of which
type of the control structure, and the appropriate set of inference algorithms,
should be based on the desired characteristics of the eventual system.
For example,
the complete OSS is expected to perform a variety of different tasks
-- from determining the type of the spill to performing various
remediation tasks, such as notifying the authorities.
Another important characteristic of this job is the timeliness and ordering
of these tasks --
the importance of recording the name of first witness dwindles when
compared with telling him not to breathe the toxic fumes.
Hence determining the toxicity of the vapors should be of tantamont importance,
especially when the leak might be near people.
A well structured agenda seemed ideally suited to these specifications.
(An additional plus was that
even this still immature RLL system already had this program construct.)
This Control subsection has three other parts. The first is simply
a quick behaviour sketch of this overall mechanism. The second part goes
into more detail, describing how these chunks of code were generated,
encoded, and processed.
These descriptions seem to imply the RLL must, necessarily, be hideously slow.
This is NOT the case.
The third part specifically addresses the issues of speed and efficiency --
a sufficiently important, and misunderstood,
point that it deserved to be included in this description of RLL.
!2.4.1.3.1 Overview of Agenda Mechanism
The agenda contains an ordered list of tasks, which are processed sequentially.
Each task is designed to performs a particular bitesize job.
For example, the goal of one task may be to determine the values
of some parameters, (e.g. the task MatType attempted to deduce
the type of material which had spilt,)
another may add other tasks to this agenda,
(for example, the task in charge of effecting the Countermeasures added
several new tasks to the agenda - one to notify the authorities, another to
begin the clean up process, etc.)
and a third type would print out instructions/requests to the user
(eg "go to Manhole #34 and tell me if you see oil").
There were several other (pre-existings) kinds of tasks
which were not necessary for this particular domain --
for example, one type could suggest and create a new concept,
while another might decide to rearrange the tasks on the current agenda
in recognition of some new fact.
In general, executing a task involves
first collecting relevant rules, then ordering and firing
this list in sequence.
(For this limited oil spill project, this collection step was trivial --
it was simply looking up the set of rules pre-stored on each particular task.)
There are many types of rules, each charged with (attempting to) achieve a
different type of goal.
(In this sense they are similar to tasks, only in a smaller scale.)
Some rules employ a known technique (algorithm) to evaluate
the value of some attribute.
(For example, determining the toxicity of a given material by looking
it up in a table.)
Others may decide to add additional rules to this rule-set,
or propose adding a particular new task to the agenda.
Still others may suggest that the current task (in which this rules occurs)
be suspended, to await necessary new data.
(Note the flow of command is quite structured.
Each rule, task or agenda* can only effect its immediate surroundings.
More global changes are performing to sending messages to its overlord,
proposing this alteration.)
* Footnote: RLL (EURISKO) is capable of dealing with several agendae --
swapping among them as need arises.
This facility was one of many RLL features which were not needed
for this job.
!2.4.1.3.2 The Details of the Agenda Mechanism
We chose to view each part of the overall control as a process --
each operation took some prescribed type of input, and performed
some action, possibly returning a result.
As sketch in the previous subsection, the "Agenda-Processor" looked like this:
Initialize <Agenda>
Loop thru <Tasks>:
Get next <Task>, T
Process T
PostMortem <Agenda>.
The "Task-Processor" is (not surprisingly) similar:
Initialize <Task>
Loop thru <Rules>:
Get next <Rule>, R
Process R
PostMortem <Rule>.
as is the overall OSS Process -
Initialize <OSS-System>
Loop thru <Agenda>:
Get next <Agenda>, A
Process A
PostMortem <OSS-System>.
This commonality was factored out, and exploited by defining the
EuriskoProcess * unit, shown below,
as a common "ancestor" to both task-processors and agenda-processors
(as well as other types and levels of control structure - such as the overall
top-level systems for both Eurisko and this OSS projects).
[*fnnote: RLL was developed as the underpinnings for the EURISKO project,
described in [?]. As this system relies on a sophisticated, and modifiable
agenda mechanism, this control structure was the first one developed and
incorporated into RLL.]
-----
AnyEuriskoProcess
Isa: (AnyClassOfObjects)
SuperClass: (AnyProcess)
SubClass: (AnyTaskProcess, AnyAgendaProcess, ...)
Examples: (FullEURISKO-System, FullOSS-System ...)
TypicalExample: TypicalEuriskoProcess
...
TypicalEuriskoProcess
TypicalExampleOf: AnyEuriskoProcess
FunctionalSlots: (LispFn ToInitialize ToSelectNextSub ToXeqSub
ToPostMortem)
...
-----
Now defining the task processor is fairly straightforward --
first create the OSS-TaskProcessor unit as an example of
AnyTaskProcess, and then fill in the values of its functional slots:
ToInitialize, ToSelectNextSub, ToXeqSub, and ToPostMortem.
(As we'll see in a moment, the value of LispFn is generated from these
components. As such the user is NOT expected to enter this value.)
Actually the user's chore is further simplified as any of these slots
he leaves unspecified defaults to the value of the corresponding slot of
TypicalTaskProcess. *
[*fnnote:
This only works because the various involved slots are all "inheritable
slots" -- ie their respective values can be determined by following
the inheritance paths; and because
the first prototype these tasks will find is TypicalTaskProcess.]
-----
AnyTaskProcess
Isa: (AnyClassOfObjects)
SuperClass: (AnyEuriskoProcess)
SubClass: ()
Examples: (OSS-Task-Process)
TypicalExample: TypicalTaskProcess
...
TypicalTaskProcess
TypicalExampleOf: AnyTaskProcess
ToInitialize: DefaultTaskInitializer
ToSelectNextSub: DefaultRuleSelector
ToXeqSub: DefaultRuleProcessor
ToPostMortem: DefaultTaskPostMortemor
...
-----
These "functions",
DefaultTaskInitializer, DefaultRuleSelector, etc., are themselves units,
which the user can examine and modify, if desired.
The "LispFn" of this OSS-TaskProcessor is now filled in, by connecting the
code present (or virtually present) in the various functional slots of the
OSS-TaskProcessor unit, to correspond to the schema shown in above.
Unfortunately, at this point, no one (or rather, no task)
knows about this nice assembled clump of code.
To tie it in, each task which wants to use it must point to this
OSS-TaskProcessor. Setting the value of Task#34:ToProcessMe to
OSS-TaskProcessor achieves ths effect.
In fact, as the value of this ToProcessMe slot is inheritable, setting
the value of
TypicalOSSTask:ToProcessMe to this OSS-TaskProcessor means everything
which includes TypicalOSSTask as a prototype will use
OSS-TaskProcessor by default
-- unless the user, wanting
a different task processor to be used for this particular task,
explicitly stored the name of that processor on this slot.
Creating the OSS-AgendaProcessor is quite similar,
here exploiting facts stored on TypicalAgendaProcessor as needed.
You may note that it is the Agenda controller which decides what to do
with each task. By default, each agenda "processes" each of its tasks,
using the mechanism which looks on that task's ToProcessMe slot, and
calls that function on this task. Of course, the agenda is not forced
to do this -- it may "know better", and use some other task-processor --
for example, on which is less accurate but quicker, for all the tasks.
Or it may only use this power sometimes, for example, if the agenda processor
is told that storage space is low, or whatever.
!2.4.1.3.3 Efficiency
From the above descriptions, one may infer that RLL is actually
"executing" high level
specifications of various control algorithms that the user input.
Were this true, RLL would have sacrificed any hope for speed and
(time-)efficiency for the sake of flexibility.
That is NOT the case.
As we showed earlier
(footnote on p. ?), RLL preserves both these high level descriptions
definitions, AND what these forms "compile" into -- and it
is that latter body of fast code which is actually run.
Much of RLL boot-strapping code is devoted to maintaining
these correspondences --
so that any change to a high level form marks the (formerly-)corresponding
executable code as invalid. On demand (that is, the next time that code
is needed,) RLL will expand that new high level definition into runnable
code; and store these low level forms so they will accessed speedily
next time the code is needed.
Returning now to the question of efficiency, we see that RLL's code
can be arbitrarily fast.
Rather than "interpret" the high level descriptions, RLL first "compiles"
these into efficient forms, and runs this faster code.
This costs only a constant overhead -- for the one time charge of
expanding that terse description. From there on the code can be
arbitrarily efficient.
Basically RLL has paid for its flexibility in terms of space -- to maintain
the different versions of the code -- and not in time.
More details on how these multiple versions are maintained, used and cached
can be found in [Lenat et al] and [Greiner].
!2.4.1.4 System Facilities
WINS
The report, so far, has emphasized RLL's strengths
which derive from it's "competence model" of programming in general,
and of the data structures and algorithms it uses in particular.
Many of its other wins are due to its environment.
Because it is is built on top of CORLL,
a demand paging system [CORLL],
RLL is able to
ignore InterLisp's 256K storage maximum,
and store an almost unlimited number of units.
Other big advantages come from InterLisp itself --
including things like spelling correction and inline editors.
LOSSES
RLL's biggest problem, at this stage of its development, is its immaturity.
By design, it will continuously incorporate new facts about control structures,
forms of representation and modes of inheritance.
However, OSS was built way too early in this ongoing design process.
For example, RLL had never encountered a Solvable Problem before --
all of its previous work had been directed towards AM-like searches --
things which never terminal with a final verdict (ie RLL knew about tasks
like "Find examples of primes", but not about things like "What is the source
of the spill").
Another big weakness, which also stemmed from its youth, was its lack of
a user front end. A trivial example involves the way we were forced to
enter the code -- everything was in a LISPy (GetValue 'Material
'Name), rather than a nicer "Material's name".
At a deeper level, RLL did not yet have any notion of context --
this forced us designers to explicitly type (continuing the above example)
"Material name" rather than the (sufficient) "name".
A good front end could have aided in the design of this system, by suggesting
appropriate data structures and algorithms as we went. This too was missing.
Another system related short-coming, again ephemeral, is RLL's dependency on
InterLisp. Our long term plans are to build RLL into a module which can
be run in MRS [MRS] (we'll return to this point in the Conclusion).
RLL will, at that point, inherit
the machine and LISP-dialect independence of MRS.
RLL's final major fault seems almost paradoxical:
it was it's immense adaptability.
Too much freedom, we found, forced us to spend considerable time
deciding which really was the best.
This time, of course, was not ill-spent; the final OSS is certainly
better than the product of any system which forced out hand at each step,
molding our final code to match the ESBp's limited set of usable components.
However, as such external constaints would certainly have
narrowed down our search, we might even have finish the system in the
four days we were allotted.
Once again this type of problem could have been alleviated in a more
mature system, which included a competent front end which would have
served as "gentle guide" during this building process.
!2.4.1.5 Conclusion
We will conclude win a perspective of RLL -- in terms of its past, its
current status, and our long term plans.
Two years ago,
RLL began as a two week project to build a representation language on
which the EURISKO system would be built.
We soon realized many non-trivial research issues had to be addressed before
such a general, "self-encoding" language could be constructed.
(We eventually abandoned the quest for this ultimate language, satisfying
ourselves with the generality which was possible within a limited set of
constraints. The more theoritical aspects of this representation language
language work was taken up
by other members of the HPP community; and their next step is described in
[MRS].)
The current system plays a necessary boot-strapping role -- certain parts
of the system must be present, as these are used to fill in other parts.
(For example, the code which is used to expand high level definitions must
be present -- or at least enough of it to generate the rest of the
itself.)
In the long run we will actually build RLL into the MRS system -- viewing
each of the seperate decomposable parts of this systems as an MRS module,
which can be individually or collectively plugged in (ie activated).
Using MRS as a Lingua Franca, RLL will be able to absorb a large corpus
of knowledge and examples from a multitude of users -- the MRS community.
Each of these other modules will hold facts about a particular domain, or
part of that domain -- eg Medical tutoring, VLSI design, or planning experiments
in the field of Genetics.
For its part,
these RLL-based MRS modules will store facts about certain types of representations,
together with their major applications.
Important in this list will be expertise about expertise.
It is this knowledge which will enable RLL to fashion new ESs with greater
efficient and accuracy.
BOTTOM LINE
While other ESBp systems have proven expedient for tackling particular problems
in particular domains, such systems seem inescapably limited
in the scope of problems they can solve.
We feel this problem is intrinsic to such ESBps, at least until
they, like the human programmers they are trying to emulate,
are capable of a crude understanding of the code they are attempting to
to compose -- an understanding which is far deeper
than the superficial level any current system (including RLL) has yet achieved.
RLL was written with the goal of attaining this necessary
undertanding.
! BIBLIOGRAPHY
[Greiner80] - "RLL-1: ..."
[Greiner & Lenat80a] - AAAI
[Greiner & Lenat80b] - Details of RLL
[Lenat, Hayes-Roth, & Waterman] - Cognitive Economy
[Smith] CORLL
[Genesereth, Greiner & Smith] - MRS
CHI, FOL, LISP...
RLL subChapter in BES book
∂14-Oct-81 0932 jackie at RAND-UNIX RLL chapter
To: RDG at SU-AI
Russ:
Here is the portion of a document I am writing that deals with your
language. This will become part of the final report on the expert
system workshop. It is a summary of the report you made about the
workshop experience.
Please read this carefully and correct any errors or misconceptions
on my part. The only constraint is that the text length must not
increase. The report goes to publication on October 22, so please
respond by October 20 at the latest (1 week from now).
Thanks for your help,
Don
##################################
∂TO DON@Rand-Unix, JACKIE@Rand-Unix, CSD.LENAT@SCORE 17:19 19-Oct
RLL chapter
Don -
Sorry to force you into so massive a rewrite. It appears the document
I was writing was an order of magnitude more detailed than you wanted...
I made a few corrections to the document.
Many of the comments are changing "modalities" -- to give the report
a higher intersection with reality.
Others are pointers to references, which the interested reader can then
follow.
Anyway, the lines preceeded by "***" are the original;
my changes are flagged by ">>>".
(IE deleting the lines beginning with "***" leaves you with
my alterred report; deleting the ">>>" lines leaves the paper you sent.)
Thanks for you giving me a last word,
Russ
##################################
CASE STUDY 6: RLL
Overview of RLL
RLL is a
>>> structured
collection of tools to help the knowledge engineer
construct, use, and modify expert systems (Greiner and Lenat, 1980,
Barstow, et al., 1982). In one sense RLL is itself an expert system
*** -- knowlegable
>>> -- knowledgeable
in facts about programming in general,
and its own subroutines in particular. This competency permits RLL to
"understand" its internal inference procedures, and provides the
user with a means for modifying these programs to meet his
specifications. The RLL system contains a collection of constructs
useful to the knowledge engineer, including different types of
slots, control mechanisms, inheritance schemes, and methods of associating
*** procedures with relevant knowledge.
>>> appropriate actions to help access particular facts.
RLL organizes
these constructs into a library to help the user access them and
provides tools to help the user manipulate, modify and combine
them. For example, if the user decided he needed a new type of
slot or inheritance procedure he could create one by performing a
*** simple modification to a similar existing one.
>>> simple modification on a similar existing one.
Furthermore, with RLL the user can create new modes of inference using the same types
of steps a program like CASNET would use to incorporate a new fact
about a patient, or a new type of disease. RLL allows the
specifics of the problem to guide the nature and implementation of
the final system -- rather than force the system into some
particular formalism. Thus the knowledge engineer has great
latitude in determining the type of control, as well as the form of
the data.
Problem Considered
The RLL team concentrated on the general crisis management
problem with special emphasis on determining the source location.
They considered subproblems ranging from identifying the spill
material to performing remediation tasks, such as notifying the
authorities. The problem of dealing with the timeliness and
ordering of subtasks was also considered (e.g., recording the name
of a witness to a toxic acid spill should be deferred until
*** he is
>>> after he has been
warned not to breathe the fumes).
Design of the Resulting System
The RLL team decided their model would play the role of the
spill crisis management expert. Thus the model coordinates a
number of tasks, including directing the activities of the spill
observers, sending out new teams, and notifying authorities.
The RLL model incorporates facts ranging from very general
statements about spills to specific connections between manholes in
the drainage basin. Also included are representations of events,
such as "oil spilling into a body of water causes a sheen." Both
facts and events are represented as RLL "units."
>>> (RLL inherited these constructs from KRL and the Units package. See
>>> [Bobrow & Winograd] and [Stefik] for additional information.)
Control of the model is based on an agenda mechanism
containing an ordered list of tasks to be processed sequentially.
Each task is designed to perform a particular job, such as
determining the spill material, implementing countermeasures or
printing instructions to the user. Tasks may add new tasks to the agenda,
e.g., the implement countermeasures task
*** might add tasks for authority notification or spill containment.
>>> adds tasks for authority notification and for spill containment.
Task execution
involves collecting relevant rules, ordering them, and firing the
list in sequence. The rules may determine new information, add
additional rules to the current ruleset, add new tasks to the
>>> current
agenda or suspend the current task to await necessary new data.
The RLL team attempted to make the model as general and
extensible as possible. Each piece of knowledge
*** added to the model
*** was generalized or abstracted. As a result, most of the model's
*** knowledge is usable in both the oil spill problem and
>>> was added to the
>>> appropriate place in the model, connected to the appropriate
>>> generalization. As a result, this model's knowledge could easily be
>>> extended beyond the oil spill problem, to handle, for example,
the convict problem (locating an escaped convict by tracing the
roads he could travel).
The team chose to sacrifice "performing a flashy demo"
for "representing things the right way"; but had to sacrifice both
to get even a meager demonstration program running. A transcript
of the RLL model being applied to the spill problem is given in
Appendix E.
Evaluation of RLL
RLL's strengths derive primarily from its "competence
model" of programming and of its own data structures and
algorithms.
*** Thus RLL models can reason about their own operation
*** and manipulate their own data structures in a very general way.
>>> Thus an RLL model can reason about its own operation
>>> and manipulate its own data structures in a very general way.
*** An example of this generality is the ease
>>> This generality was demonstrated by the ease
with which the RLL team
abstracted the model to handle a broader class of problems.
An example of the modifiability of an RLL model is fact that the RLL
team could
>>> (and did)
easily modify the RLL task interpreter to change the low
level control of the model. RLL pays for its flexibility in terms
of space rather than time.
>>> (This is explained in [Lenat, Hayes-Roth & Klahr, Cog Sci],
>>> and particularized in [Greiner, RLL].)
To offset the additional space requirements, RLL
*** has the capability to ignore InterLisp's 256K
*** storage maximum, using a demand paging algorithm.
>>> uses a demand paging algorithm to
>>> ignore InterLisp's 256K storage maximum. (See [Smith, CORLL].)
*** A major weakness of RLL is its lack of a user front-end.
>>> RLL has several major weaknesses, all stemming from its immaturity.
>>> Its lack of a user front-end proved a serious limitation.
All code for the spill model had to entered in a Lisp-like format.
A good front-end would have facilited the system design by
suggesting appropriate data structures and algorithms.
[[[ I shifted the order of the next two paragraphs. ]]]
*** A third weakness of RLL is its lack of constraints.
>>> This problem was exaggerated by RLL's lack of constraints.
The RLL team found that too much freedom forced them to spend
considerable time deciding which really was the best representation
and control structure. Some external constaints might have
narrowed the search and helped them finish their program in the
alloted three days.
*** A second weakness is its immaturity.
>>> A third weakness is RLL's current "ignorance".
By design, it will
continuously incorporate new facts about control structures, forms
of representation and modes of inheritance as it encounters new
applications. However, when the RLL spill model was built RLL had
never encountered a "solvable problem" before -- all its previous
work had been directed towards AM-like searches (Lenat, 1977). RLL
knew about tasks like
*** "Find examples of primes,"
>>> "Find examples of primes",
but not about tasks like "What is the source of the spill".
The experience of the RLL team with the spill program
illustrated that under very tight time constraints a simpler
language such as EMYCIN or LISP could achieve results more quickly
than RLL. It also reinforced their view that building an expert
system is an incremental approach to competence.
[[[ Is this \/ from Appendix E? If not, what is in that appendix? ]]]
Knowledge 1: M6-2 feeds into M6-1.
This piece of knowledge is static knowledge that represents
a piece of the drainage network in the spill problem. It says that
pipe M6-2 feeds into pipe M6-1 in the network. This knowledge
would be used to help define the topology of the drainage network
so it could be searched.
RLL Representation. This is handled within the units
framework, using units that represent M6-1,
*** M6-2 the "feeds into" relation, and the manhole concept.
>>> M6-2, the "feeds into" relation, and set of all the manholes.
M6-2
Isa: (AnyManhole)
FeedsInto: (M6-1)
M6-1
Isa: (AnyManhole)
FeedsFrom: (M6-2)
AnyManhole
Examples: (M6-1, M6-2)
Description: The class of all manholes.
FeedsInto
Isa: (AnySlot)
Description: This slot maps from manholes to manholes.
Inverse: FeedsFrom
Definition: [Lisp code that indicates how to deduce the value
*** of the slot, e.g., the manhole it maps into.]
>>> of the FeedsInto slot of some manhole, i.e.,
>>> the manhole it maps into.]
Knowledge 2: All Permanent Storage Tanks Are Diked.
This knowledge can be represented either statically or
procedurally and means that all the permanent storage tanks have
walls or ditches to insure that spills will be contained.
*** RLL Representation. In RLL this would be represented as
>>> RLL Representation. One way to represent this in RLL involves
two units: AnyStorageTank and a universal variable (called x).
AnyPermanentStorageTank
Description The class of all permanent storage tanks.
UnivElements: (x)
X
UnivIsa: (AnyPermanentStorageTank)
MyDefiningSlots: (UnivIsa TimeOfStorage)
MyAssertionalSlots: (Diked?)
*** Description: All facts stored here are true for all
>>> Description: The facts stored here are true for all
permanent storage tanks.
TimeOfStorage: Permanent
Diked?: T
Knowledge 3: If The Chemical Is HF,
Then Tell The Observer Not To Breathe It.
This knowledge is cleary procedural and is an important
warning that should be given as soon as the chemical is identified.
RLL Representation. The information can be represented as an
RLL rule as shown below:
Rule#332
Isa: (AnyRule)
IfTrulyRelevant: ((EQ 'Chemical HF))
ThenTellUser: "Do not breathe the chemical!!"
Priority: High
OnTask: ImminentDanger
>>> Note the unit above shows only what the user would have to tell RLL.
>>> The system can now compute the value for many additional slots as needed.
>>> The various slots which store executable LISP code
>>> (correspond to these declarations) are computed in this way.
∂27-Oct-81 1448 mary at RAND-UNIX References
To: RDG at SU-AI
Cc: mary at RAND-UNIX
Russell Greiner:
In the corrections for Don Waterman's document, you make
reference to Smith, CORLL. Do you have the whole
citation for the paper? Thanks.
Mary at Rand-Unix
∂TO MARY@Rand-Unix 16:38 27-Oct
CORLL paper
You probably want some subset of this:
Smith, David E., "CORLL Manual, A Storage and File Management System
for Knowledge Bases", Stanford Heuristic Programming Project,
Memo HPP-80-8 (Working Paper), November 1980.
[11 pages]
Anything else I can provide?
Russ
[DBL's version, from last page]
(17 July 1981)
Draft of RLL section of Building Expert Systems
2.4.1 RLL
Expert systems evolved to help (human) domain experts manage both the bulk
and the complexities associated with knowledge-intensive tasks. One
interesting and important observation is that the task of building expert
systems is itself a suitable one to make the target of an expert system.
This realization triggered the development of RLL, a representation
language language.
RLL is, first, a collection of tools which help the knowledge engineer
(KE) construct, use, and adapt expert system programs. In addition, it is
itself a bona-fide expert system -- knowledgable in facts about
programming in general, and its own subroutines in particular. This
competency permits RLL to "understand" its internal inference procedures,
and provides the user with a mechanism -- simple editing of the
descriptions of those subroutines -- for modifying the RLL environment to
suit his current task. All too often, KEs have had to twist the facts,
rules, relations, etc. of a task in order to fit it into some rigid
representation scheme.
This section will quickly overview this RLL system, taking examples from
our experience coding up OSS -- the Oil Spill System. We hope to show the
gains from self-describing and self-modifying software, as well as
presenting techniques for recapturing any of the efficiency lost by going
down this route.
!2.4.1.1 Overview of RLL
The hallmark of an expert system is competence in some task domain.
Usually, this does not extend to comptence in meta-cognition, an ability
for a program to reason about its own structure and behavior. MYCIN,
e.g., doesn't "know" that it uses a backward chaining inference engine to
perform its deductions, let alone WHY it uses such a control structure.
AGE, e.g., cannot answer questions about the efficiencies of itself or of
the programs it write, nor can it modify its basic Blackboard model to
handle, say, a different type of rule.
RLL begins, as does each KE himslef, with a library of useful, common
types of slots (IsA, Inverse, RangeType, and several hundred others)
control mechanisms, (backward chaining, agendae, and a few others) and
inheritance schemes. Each of these is represented internally in RLL as a
unit, a frame-like data structure of attributes (slots) and values. Thus,
each kind of slot, each kind of control scheme, each inheritance mode is
described within RLL's formalisms. Some of the units are standard
mechanisms for modifying "domain knowledge", and they can now serve to
modify any part of RLL itself. One dangerous consequence of this
philosophy is that they can modify themselves, perhaps destroying the
ability of the system thenceforth to be self-modifying.
At any moment, some ensemble of the units are combined into a description
of the desired current system, and RLL behaves in the prescribed manner.
That ensemble defines a representation language which the KE can "freeze"
if he desires, and use for some particular application he must build.
This is the reason we call RLL a representation language language. No
single set of starting primitives could possibly satisfy all of the users
all of the time.
To help the KE tailor the language to his current task, RLL provides a
number of tools (all represented as RLL units, of course) which the user
can use in constructing his own pieces, and in combining pieces into
ensembles. For example, the user can easily create a new type of slot or
inheritance procedure. Typically, he would copy a similar existing unit
and edit that copy. RLL then "compiles" the changed description into
executable code.
RLL's competence model of programming comes in at this point. There are
many indirect ramifications which arise when, say, a new laboratory
technique is added to Molgen's data base; similarly there are a host of
actions which must be taken when some part of the underlying
representation is changed. Just as Molgen's code is responsible for
propogating the effects of this new data, so the overall RLL system will
find the parts of the system which may be affected by this change, and
update these pieces appropriately.
RLL allows the specifics of a problem to guide the nature and
implementation of the user's final ES -- rather than force the system into
some particular formalism.
The reaminder of this section fleshes out our so-far skeletal description
of RLL. Subsection 2.4.1.2 explains how facts are represented in RLL ,
and shows how this structure is adequate to handle knowledge about both
the particular domain (eg Oil Spills) and RLL internals themselves (eg
facts about slots or control mechanisms). This section includes a
concrete example, using RLL's management of rules to show first how the
facts are stored, and then how various type of modifications can be done
-- ie how RLL has attained this degree of flexibility. Section 2.4.1.3
describes the control structure used for this partcular OSS application,
in a fair amount of detail. This section also explains how RLL can
provide the self-describing and self-modifying abilities discussed
previously, and yet retain (recapture) almost all the efficiency of a
hand-tailored system. The final two sections describe how RLL fits into
the world, and what yet remains to be done.
!2.4.1.2 Knowledge Representation in RLL
RLL is based on the "To every thing, a unit" philosophy. This uniform
representation system extends to all domain knowledge (e.g., units for
each type of oil and each pipe junction), and also to all repreentation
knowledge (e.g., units for the Viscosity type of slot and for the
BackChain control regime).
*--------*--------*--------*--------*
M6-2
Isa: (AnyManhole)
FeedsFrom: (M6-3 M6-2)
FeedsInto: M6-9
AnyManhole
Isa: (AnyClassOfPhysObjects)
Examples: (M6-2, M6-3, ...)
Description: The class of all manholes.
Isa
Isa: (AnySlot)
Inverse: (Examples)
Description: The slot signifying membership in a class.
MakesSenseFor: (Anything)
FeedsFrom
Isa: (AnySlot OilSpillConcept)
Inverse: FeedsInto
Description: The slot naming the upstream manholes.
MakesSenseFor: (AnyManhole)
*--------*--------*--------*--------*
RLL is, for better or worse, committed to using a particular
representation at its heart, though the apparent one seen by the user may
easily be changed, and in principle the innermost RLL might be as well.
That representation comprises a semantic network, with each node being a
structured frame-like "unit" whose attributes (slots) are defined with a
set of property-value pairs. We will show below the great flexibility RLL
does provide, within this constraint. We use the notation Oil:Isa to
refer to the value of the Isa slot of the unit Oil.
The first unit in the box above refers to a specific objects which exists
in the real world -- M6-2 represents manhole #2 on waterline #6. The next
unit represents a class of physical objects; AnyManhole encodes facts
about the set of all manholes. The next two units represent kinds of
slots. Of course there are dozens of slots absent from the units in the
figure (e.g., Worth of M6-2, Cardinality of AnyManhole, Format of
FeedsFrom).
Some types of units (e.g., those representing events) can have varying
degrees of generality. Consider an example: We may want to say general
things about oil spilling into a body of water -- eg, that it causes a
sheen. Ideally all such facts should be stored in one place, say the
OilSpillingIntoWater unit, in such a manner that every more specialized
case, will automatically inherit these facts. We want RLL to conclude
that oil spilling into a stream will cause a sheen in that stream once it
knows that OilSpillingIntoStream is a specialization of
OilSpillingIntoWater. We could go on to describe facts about
OilFromPipe93SpillingIntoWOC, a unit which, in turn, can be further
restricted into MachineOilFromPipe93SpillingIntoWOCAfterOutFall93, which
can be restricted to
DayOldMachineOil#2FromPipe93'sFirstOutletSpillingIntoWOC-
AfterOutFall93onAug23. Clearly we do NOT want to spawn a new unit for
every point in n-dimensional space. A new unit is never produced
arbitrarily, but rather only when there is some pertinant fact to preserve
about the event. When the fact is general, it goes on a general event
unit, which enables its descendants to inherit these facts.
The mechanism for handling this type of inheritance is distinct from the
more standard ElementOf or SubsetOf relations, and should be treated as
such. RLL insures this seperation by allocating different units to store
facts about each type of inheritance. Various properties of these
inheritance-defining units indicate how to initialize a new unit (as
stating that Pipe#33 is an Example of AnyPipe should be handled quite
differently from the statement that OilSpillingIntoStream is a
Specialization of OilSpillingIntoWater), or how the values of some slot
may be altered, to maintain this particular inheritance relation. (eg the
SubstanceSpilt of any Specialization, S, of OilSpillingIntoWater must be
some refinement of Oil, whereas S:TimeOfSpill can be arbitrary.
Analogously Pipe#33 can have slots like Length or TimeOfCreation, but not
things like Father or RangeType.)
Exactly how such data is encoded is far too detailed (and irrelevant) for
this report; the important fact is that such facts can be stated precisely
and explicitly in RLL. Furthermore, such facts can be altered by the
user, if his task demands it. Indeed, the user can even create new
"representational pieces": As none of RLL's prior tasks had needed this
Specialization inheritance, our starting system did not have this
particular feature. While doing the oil spill task, we designed this
totally new mechanism, and incorporated it into RLL. This is an example
of a kind of change which takes minutes in RLL, and is impossible or
awkward for most other languages. Note that this feature is now a part of
RLL -- subsequent users can now use this type of inheritance, as easily as
any of the other ones RLL "always" provided. We envision RLL will be
constantly growing -- largely through additions provided by its users.
Slots are another type of representational piece. As with inheritance
modes, the information relevant to each type of slot is stored in a unit.
The unit below shows that: The value of x:FeedsInto must be a list of
manholes, the only x for which x:FeedsInto is defined is a manhole, and
that if x:FeedsInto = y, then y:FeedsFrom = x (i.e. FeedsInto:Inverse =
FeedsFrom).
*--------*--------*--------*--------*
FeedsInto
Isa: (AnySlot)
Description: The slot naming the downstream manholes.
Inverse: FeedsFrom
HighLevelDefn: (Composition OtherEnd ConnectedPipes)
MakesSenseFor: (AnyManhole)
Format: SingleElements
Datatype: Unit representing a manhole.
ToCompute: (λ (u) [Find the pipe, P, to which this manhole connects.
See which pipe, p', to which this P is connected.
Return the manhole m, which is connected to
pipe p'.]
Note - the ToCompute of a slot indicates how to deduce its value -- i.e.
S:ToCompute is a function, F, whose value, (F u), is the value to fill
u:S.
*--------*--------*--------*--------*
It is important to realize that those facts shown above are not JUST a
description of the FeedsInto type of slot -- it really is used to define
this slot. If any of those slots were ever changed, the way this slot
behaves would be affected. For example, resetting FeedsInto:Format to be
SetOfElements (rather than SingleElement) would cause RLL to redefine
FeedsInto:ToCompute to return a singleton list rather than a single atom
(corresponding to that manhole,) and to (retroactively) fix up each value
of u:FeedsInto. If that value were empty, it would remain empty.
Otherwise the single value v would be changed into the list (v).
Similarly, each data structure -- each rule (condition/action heuristic),
task (small local goal), and agenda (list of tasks dealing with a single
topic) -- is stored as a unit. This permits the data to dynamically
altered during the course of the computation, or through user input. That
is, one uses the same procedures to add in a new unit, independent of
whether that unit represents a new rule, a new pipe, or new type of slot.
Even the procedures of this system are encoded in units -- notalby
including the parts of the control structure outlined below. As with
parts of the repesentation, these facts are actually used as the system is
run. Editing the units describing them will result in changes in the flow
of control of RLL. For brevity, we will address details of only one of
these chunks -- the rules. Section 2.4.1.4, which overviews the contol
structure actually used, will then sketch the other parts of the system's
control, emphasizing the advantages which come from "unitizing" these
parts.
!2.4.1.2.1 Example - How RLL Encodes Rules
Each rule has a number of obvious attributes. The primary facet of each
rule is the actual code which is to be executed. RLL spares the user the
arduous task of entering the actual LISP expression to be run; instead the
user can type a more laconic high-level specification of what this rule is
to do. RLL then "expands" this definition into that executable code.
(This is done in a very general, RLL-ish manner, using facts stored in the
name of the slot. Hence it is the unit associated with the ThenTellUser
slot which "knows" to expand a message, like
("Do not breath this chemical, " Chemical "!!"
" It is " (Toxicity Chemical) ".")
into code which prints it when the user is present --
(PROGN (WriteToUser "Do not breath this chemical, " (GetVal Chemical) "!!")
(WriteToUser " It is " (GetVal (Toxicity Chemical)) "."))
)
*--------*--------*--------*--------*
Rule#332
Isa: (AnyRule)
Description: Tell the user to hold his breath if the chemical is toxic.
IfPotentallyRelevant: (APPLY ToxicP Chemical)
IfTrulyRelevant: (APPLY NearbyUser ChemicalHasSeepedTo)
ThenTellUser: ("Do not breath this chemical, " Chemical "!!"
" It is " (Toxicity Chemical) ".")
ThenAddToAgenda: EmergencyProcedures
Priority: High
OnTask: (ImminentDanger)
ImminentDanger
Description: This task tries to find if the current situation is
dangerous; and if so, suggest solutions/fixes/alternatives.
Isa: (AnyTask)
RuleList: (Rule#332, ...)
EmergencyProcedures
Description: This task is called iff the current situation is dangerous;
and issues many quick-and-dirty orders.
Isa: (AnyTask)
RuleList: (Rule#981, ...)
- Note the rule above is what the user would type.
RLL would use this to compute the actual to-be-run code, as it was needed.
*--------*--------*--------*--------*
There are several major advantages to providing both high and low level
forms of a rule specification. In addition to facilitating the creation
of a new rules, this higher level makes the nature of the rule easier to
understand and reason about, for both the user and RLL itself. RLL is
able to use different versions of the definition of the procedure or slot
for different type of tasks, in much the same manner that InterLisp
handles both compiled and interpreted forms of each function. When a user
wishes to examine or edit a function, IL pulls in that function's source
listing, rather than force the user to peruse LAP code. However it is
that low-level LAP code which IL actually runs. Similarly when someone
wants to examine a rule, (ie estimate how long it will take, or determine
what sorts of things this execution will affect,) the rule's concise
"declarative" form of the specification is offered. This, of course, is
NOT the form which is actually run. The much-less-perspicious expanded
form is used for this purpose. This also represents a sizable savings of
run-time speed. Section 2.4.1.5.3 addresses this, and related, issues.]
The example above shows how the specifications for this rule are scattered
about, stored in several distinct slots. This permits different parts to
be executed independently -- for example, allowing the quick IfPotentially
check to run to all of wide class of rules; and then running the more
expensive IfTrulyRelevant part only on that small subset which passed.
The THEN parts are also split up. In common practice, once the IF-parts
have all passed, each of the THEN parts is run, in the appropriate order.
The description above is the way a rule is evaluated "by default" -- that
is, unless the user has something else in mind. Recall any user can
readily modify that rule-evaluating procedure as well. So, for example,
the user may decide instead to execute the code stored on the
IfWorkingOnTask slot of a rule, or IfTodayIs, or any other set of slots.
rather than the current IfPotentiallyRelevant and IfTrulyRelevant slots
now used. In getting EURISKO running, Lenat had to define three additional
rule interpreters of this sort, though most of them refer to the same
kindsof If- and Then- slots of rules.
The user may also decide to compose a single Total-IF-Part, which ANDs
together all of the different types of If-parts. Similarly he may want
the THEN parts executed in a different order; or may have decided to only
run those THEN parts for which he has sufficient resources.
Note that this could not be done if each rule were simply a single piece
of compiled code, or only a double lump of code (IF and THEN). We claimed
above that it was easy to change the rule interpreter. This is because
that block of code is itself an RLL unit. Like the rules, it is
decomposed into nice sized chunks, which can be independently modified.
One such hook is a list of slotnames which constitute the IF part of a
rule, together with a description of when that code should be executed.
We will return to this point in the next section, which discusses the
basic control structure.
*--------*--------*--------*--------*
StandardRuleInterpreter
Isa: (AnyRuleInterpreter)
Description: This is the standard procedure used to interpret a given
rule. It first executes the AND-junction of the rule's
If-Parts. If the result is nonNIL, it executes all of
rule's Then-Parts.
HighLevelDefn: (IF (AND-Junction ProcessPart IfParts)
(AND-Junction ProcessPart ThenParts))
UsedByRules: (Rule#3 Rule#5 ...)
IfParts
Isa: (AnySlot)
Description: The value of this slot is the list of slots of the unit
(here a rule) which descend from the class, AnyIfPart.
These are ordered by the value of their respective
OrderForRuleParts.
HighLevelDefn: (PutInOrder (Subsetting MySlots
(ValueIncludes Isa AnyIfPart))
OrderForRuleParts)
MakesSenseFor: Rules
Datatype: Slots
Format: OrderedSetOfElements
Simplified version of the Standard Rule Interpreter.
Much of its code is "hidden" in the parts of the HighLevelDefn -- eg
IF, AND-Junction, ... Of course, these too are units, and are visible to the
interested user.
(The IfParts unit is shown, to dissuade those who do not believe this claim.)
*--------*--------*--------*--------*
Before leaving this rule description, there are several other
"declarative" facts which might be stored in each rule. One important
slot is the average CPU time this rule has spent, for executing its IF
parts and THEN parts, respectively. This can be used for various
meta-level reasoning tasks -- such as deciding whether to even consider
this rule in the future (ie did its bang justify its bucks).
Each rule also records, in a slot, the name of its author or creator,
which might be a person and might be another rule (rules can inspect,
modify, and synthesize other rules). This can help decide who to
credit/blame for good/bad rules; and this data can help the overall system
to improve its performance by relying more and more on capable (that is,
successful) rule writers. Finally, the user himself can store any other
type of information he wants -- these are just things which we feel may be
useful types of statistics.
Of course various inference schemes -- most importantly an inheritance
hierarchy -- are used to simplify data entry. A new rule can be entered
by merely copying that existing prototype, and changing only those entries
which are inappropriate. Hence the bulk of the properties are simply
inherited from more general ideas -- here from RLL's facts about rules in
general. *
[Fnnote*: In fact, for pedagogic reasons, we might make the novice user
master only a small subset of the slots initially present in RLL. He need
learn about other dimensions of RLL's extendability only when he begins to
complain about how awkward it is to encode this or that fact, or wonders
why he can't seem to capture some particular type of idea. Until that
time, for example, he need have nothing more that a "behaviour
description" of the rule interpreter -- which is all he would ever know
about the corresponding evaluator in most other expert systems.]
The above description of rules illustrates the degree of flexibility
available to the user at the designing stage. The current RLL includes
many rule interpreters which we, the RLL designers, felt were appropriate
and useful. It is important to realize, however, that the eventual user
is not limited to only these. Not only is he free to design his own
interpreters, but RLL aids in this mission, by providing tools which
facilitate constructing such interpreters. Indeed, as these tools are
represented in RLL as well, the user can even construct his own building
aids, if he feels the need.
There are similar mechanisms for implementing the processes used for
"running" agendae, or tasks, or other control regimes. (For example a
black board architecture, for other types of tasks.) Corresponding to
each such process is the data structure to which it applies; and RLL
includes means for extending or adapting those as well -- ways of
extending tasks, for instance.
This section tried to demonstrate how useful RLL's competence in this
programming domain is when designing and building a new expert system.
The next subsection shows another application of this facility -- when the
user wishes to modify his existing ES. Here the user has the option of
changing his mind later, and know that RLL will modify not only the code,
but perform the retroactive updates to his data required to keep code and
data in synch.
!2.4.1.2.2 RLL's Modifiability
Different system have different conventions defining what part of the
running system is changable, and which is, to all but the most
sophisticated user, untouchable. By design even casual users can enter,
change or delete "domain data" -- facts, in this case, about the
connectivity of pipes, or the precise placements of various buildings.
(Eg if the user later realizes that Pipe#406 really joined Pipe#317,
rather than Pipe#316 as he had thought.)
In many representations systems, the user can addres and modify generic
objects as well -- for example, respecify which features are well-defined
for types of roads, or redraw the taxonomical information about types of
oil. In addition to these, some languages permit the user to define
totally new types of relations -- in the form of new slots for our RLL
language. (For example, the FeedsInto slot which was handily defined as
the Composition of the OtherEnd and the ConnectedPipes slots.)
These definitions can be used to redefine the "meaning" of a slot as well
as initiate one. Suppose you realized that pipes could really join many
pipes, rather than just one. This would be difficult to say in many
languages -- indeed the only solution in most might require throwing away
that FeedsInto link and defining a totally new FeedsIntoS link. Even then
all of the existing data would have to be transfered, regrettably by hand.
In RLL, on the other hand, all of the executable code is made explicit,
and the user is permitted to modify it to suit his design. All he need do
is edit the FeedsInto unit, examine the Datatype slot, notice it says
SingleElement, and change that to read SetOfElements. As he exits the
editor, RLL makes the necessary changes and all units' FeedsInto slots
will look like singleton sets, and can have multiple entries added on at
any time.
As we earlier pointed out, RLL provides various tools for such adaptations
-- for example, the high level specification language for functions, and
the use of appropriately chunking the knowledge. (These are the same
things which proved so useful for constructing of parts -- but it is also
be exploited for retro-actively modifying existing parts.) RLL's uniform
representation of facts makes changing the code as easy as altering any
domain data -- as the facts which specifies a slot's arity is in the same
format as data about Oil#31, or any other domain or representation fact.
Furthermore, RLL's "understanding" of things like SingleElement and
SetOfElements allows it to do all the appropriate fixes, automatically.
RLL extends this modifiability to include the control structure as well.
This permits the user to construct his own form of control, as he needs
it.
The next section outlines the contol structure we found useful for this
particular Oil Spill task. We wish to emphasize, again, that this Agenda
mechanism is but one of several control structures, some implemented and
some merely envisioned -- and that the user could have designed his own
from smaller pieces supplied by RLL, using tools present in RLL.
!2.4.1.3 Control
The characteristics of the user's current domain task will strongly
influence the choice of which control regime to select, what inference
algorithms will be active, what slots will be employed, etc. For example,
the complete OSS is expected to perform a variety of different tasks --
from determining the type of the spill to performing various remediation
tasks, such as notifying the authorities. Another important
characteristic of this job is the timeliness and ordering of these tasks
-- the importance of recording the occupation of first witness dwindles
when compared with telling him not to breathe the toxic fumes. Hence
determining the toxicity of the vapors should be of paramount importance,
especially when the leak might be near people. A well structured agenda
seemed ideally suited to these specifications. The agenda has tasks of
varying levels of generality, each justified by some symbolic reasons
which yield a numeric priority value for the task. Some tasks, such as
those involving human lives, will have much higher priority than tasks
whose reasons are "long-term demographic data". As a task executes, it
may add new tasks to the agenda, occasionally supplanting what would have
been the next task to execute.
This Control subsection has three other parts. The first is simply a
quick behaviour sketch of this overall mechanism. The second part goes
into more detail, describing how these chunks of code were generated,
encoded, and processed. These descriptions seem to imply the RLL must,
necessarily, be hideously slow. This is NOT the case. The third part
specifically addresses the issues of speed and efficiency -- a
sufficiently important, and misunderstood, point that it deserved to be
included in this description of RLL. Almost all of the lost efficiency
can be recaptured.
!2.4.1.3.1 Overview of Agenda Mechanism
The agenda contains an unordered set of tasks, which are processed one at
a time. Tasks are chosen based on the priorities of the reasons
supporting them. Each task is designed to performs a particular bitesize
job, to meet a local goal. For example, the goal of one task may be to
determine the values of some parameters, (e.g. the task MatType attempted
to deduce the type of material which had spilt,) another may add other
tasks to this agenda, (for example, the task in charge of effecting the
Countermeasures added several new tasks to the agenda - one to notify the
authorities, another to begin the clean up process, etc.) and a third
type would print out instructions/requests to the user (eg "go to Manhole
#34 and tell me if you see oil"). There were several other (pre-existing)
kinds of tasks which were not necessary for this particular domain -- for
example, one type could suggest and create a new concept.
In general, executing a task involves first collecting relevant rules,
then ordering and firing this list in sequence. (For this limited oil
spill project, this collection step was trivial -- it was simply looking
up the set of rules pre-stored on each particular task.) There are many
types of rules, each charged with (attempting to) achieve a different type
of goal. (In this sense they are similar to tasks, only in a smaller
scale.) Some rules employ a known technique (algorithm) to evaluate the
value of some attribute. (For example, determining the toxicity of a
given material by looking it up in a table.) Others may decide to add
additional rules to this rule-set, or propose adding a particular new task
to the agenda. Still others may suggest that the current task (in which
this rules occurs) be suspended, to await necessary new data. (Note the
flow of command is quite structured. Each rule, task or agenda* can only
effect its immediate surroundings. More global changes are performing to
sending messages to its overlord, proposing this alteration.)
* Footnote: RLL (EURISKO) is capable of dealing with several agendae --
swapping among them as need arises. This facility was one of many RLL
features which were not needed for this job.
!2.4.1.3.2 The Details of the Agenda Mechanism
We chose to view each part of the overall control as a process --
each operation took some prescribed type of input, and performed
some action, possibly returning a result.
As sketched in the previous subsection, the "Agenda-Processor" looked like this:
Initialize <Agenda>
Loop thru <Tasks>:
Get next <Task>, T
Process T
PostMortem <Agenda>.
The "Task-Processor" is (not surprisingly) similar:
Initialize <Task>
Loop thru <Rules>:
Get next <Rule>, R
Process R
PostMortem <Rule>.
as is the overall OSS Process -
Initialize <OSS-System>
Loop thru <Agenda>:
Get next <Agenda>, A
Process A
PostMortem <OSS-System>.
This commonality was factored out, and exploited by defining the
EuriskoProcess * unit, shown below, as a common "ancestor" to both
task-processors and agenda-processors (as well as other types and levels
of control structure - such as the overall top-level systems for both
Eurisko and this OSS projects).
[*fnnote: RLL was developed as the underpinnings for the EURISKO project,
described in [Lenat The Nature of Heuristics]. EURISKO relies on a
sophisticated, modifiable agenda mechanism, which is why it was the first
control structure developed and incorporated into RLL.]
-----
AnyEuriskoProcess
Isa: (AnyClassOfObjects)
SuperClass: (AnyProcess)
SubClass: (AnyTaskProcess, AnyAgendaProcess, ...)
Examples: (FullEURISKO-System, FullOSS-System ...)
TypicalExample: TypicalEuriskoProcess
...
TypicalEuriskoProcess
TypicalExampleOf: AnyEuriskoProcess
FunctionalSlots: (LispFn ToInitialize ToSelectNextSub ToXeqSub
ToPostMortem)
...
-----
Defining the task processor is now fairly straightforward -- first create
the OSS-TaskProcessor unit as an example of AnyTaskProcess, and then fill
in the values of its functional slots: ToInitialize, ToSelectNextSub,
ToXeqSub, and ToPostMortem. (As we'll see in a moment, the value of
LispFn is generated from these components. As such the user is NOT
expected to enter this value.) Actually the user's chore is further
simplified as any of these slots he leaves unspecified defaults to the
value of the corresponding slot of TypicalTaskProcess. *
[*fnnote: This only works because the various involved slots are all
"inheritable slots" -- ie their respective values can be determined by
following the inheritance paths; and because the first prototype these
tasks will find is TypicalTaskProcess.]
-----
AnyTaskProcess
Isa: (AnyClassOfObjects)
SuperClass: (AnyEuriskoProcess)
SubClass: ()
Examples: (OSS-Task-Process)
TypicalExample: TypicalTaskProcess
...
TypicalTaskProcess
TypicalExampleOf: AnyTaskProcess
ToInitialize: DefaultTaskInitializer
ToSelectNextSub: DefaultRuleSelector
ToXeqSub: DefaultRuleProcessor
ToPostMortem: DefaultTaskPostMortemor
...
-----
These "functions", DefaultTaskInitializer, DefaultRuleSelector, etc., are
themselves units, which the user can examine and modify, if desired.
The "LispFn" of this OSS-TaskProcessor is now filled in, by connecting the
code present (or virtually present) in the various functional slots of the
OSS-TaskProcessor unit, to correspond to the schema shown in above.
But so far, no one (or rather, no task) knows about this nice assembled
clump of code. To tie it in, each task which wants to use it must point
to this OSS-TaskProcessor. Setting the value of Task#34:ToProcessMe to
OSS-TaskProcessor achieves ths effect. In fact, as the value of this
ToProcessMe slot is inheritable, setting the value of
TypicalOSSTask:ToProcessMe to this OSS-TaskProcessor means everything
which includes TypicalOSSTask as a prototype will use OSS-TaskProcessor by
default -- unless the user, wanting a different task processor to be used
for this particular task, explicitly stored the name of that processor on
this slot.
Creating the OSS-AgendaProcessor is quite similar, here exploiting facts
stored on TypicalAgendaProcessor as needed. Note that it is the Agenda
controller which decides what to do with each task. By default, each
agenda "processes" each of its tasks, using the mechanism which looks on
that task's ToProcessMe slot, and calls that function on this task. Of
course, the agenda is not forced to do this -- it may "know better", and
use some other task-processor -- for example, on which is less accurate
but quicker, for all the tasks. Or it may only use this power sometimes,
for example, if the agenda processor is told that storage space is low, or
whatever.
!2.4.1.3.3 Efficiency
From the above descriptions, one may infer that RLL is actually
"executing" high level specifications of various control algorithms that
the user input. Were this true, RLL would have sacrificed any hope for
speed and (time-)efficiency for the sake of flexibility. That is NOT the
case. RLL preserves both high level descriptions AND what these forms
"compile" into -- and it is that latter body of fast code which is
actually run. Much of RLL's boot-strapping code is devoted to maintaining
these correspondences, so that any change to a high level form marks the
(formerly-)corresponding executable code as invalid. On demand (that is,
the next time that code is needed,) RLL will expand that new high level
definition into runnable code; and store these low level forms so they
will accessed speedily next time the code is needed.
RLL's code can be arbitrarily fast. Rather than "interpret" the high
level descriptions, RLL first "compiles" these into efficient forms, and
runs this faster code. This costs only a constant overhead -- for the one
time charge of expanding that terse description. From there on the code
can be arbitrarily efficient. The first time a GET is done, or the first
time the value of a high level slot is called for after its definition has
been written or changed, there will be a pause; but the next (and future)
times there will be no noticable slowdown compared with hand-crafted Lisp
code.
Basically RLL has paid for its flexibility in terms of space -- to
maintain the different versions of the code -- and not in time. More
details on how these multiple versions are maintained, used and cached can
be found in [Lenat et al] and [Greiner].
!2.4.1.4 System Facilities
STRENGTHS
This section, so far, has emphasized RLL's strengths which derive from
it's "competence model" of programming in general, and of the data
structures and algorithms it uses in particular. Many of its other wins
are due to its environment. Because it is is built on top of CORLL, a
demand paging system [CORLL], RLL is able to ignore InterLisp's 256K
storage maximum, and store an almost unlimited number of units. Other big
advantages come from InterLisp itself -- including things like spelling
correction and inline editors.
Having all knowledge represented uniformly should be a powerful boost to
attempts at meta-cognitive systems. RLL needs this meta-level reasoning
ability, since it must monitor and model and modify itself. Furthermore,
it is possible to write new slots in terms of old ones, slots which skew
the system to be more appropriate to CAI than to performance on a task.
This may aid in realizing multiple uses from a single knowledge base.
WEAKNESSES
RLL's biggest problem, at this stage of its development, is its
immaturity. By design, it will continuously incorporate new facts about
control structures, forms of representation and modes of inheritance.
However, OSS was built way too early in this ongoing design process. For
example, RLL had never encountered a Solvable Problem before -- all of its
previous work had been directed towards AM-like searches -- explorations
which never terminate with a final answer (ie RLL knew about tasks like
"Find examples of primes", but not about things like "What is the source
of the spill").
Another big weakness, which also stemmed from its youth, was its lack of a
user front end. A trivial example involves the way we were forced to
enter the code -- everything was in a LISPy (GetValue 'Material 'Name),
rather than a nicer "Material's name". At a deeper level, RLL did not yet
have any notion of context -- this forced us designers to explicitly type
(continuing the above example) "Material name" rather than the
(sufficient) "name". A good front end could have aided in the design of
this system, by suggesting appropriate data structures and algorithms as
we went. This too was missing.
A smaller shortcoming, again ephemeral, is RLL's dependency on InterLisp.
Our long term plans are to build RLL into a module which can be run in MRS
[MRS]. RLL will, at that point, inherit the machine and LISP-dialect
independence of MRS.
RLL's final major fault seems almost paradoxical: it was it's immense
adaptability. Too much freedom, we found, forced us to spend considerable
time deciding which of many plausible options really was the best. This
time, of course, was not ill-spent; the final OSS is certainly better than
the product of any system which forced a choice at each step, molding our
final code to match the ESBp's limited set of usable components. However,
as such external constaints would certainly have narrowed down our search,
we might even have finished the system in the four days we were allotted.
We believe this type of problem could have been alleviated in a more
mature system, which included a competent front end which would have
served as "gentle guide" during this building process.
!2.4.1.5 Conclusion
We will conclude win a perspective of RLL -- in terms of its past, its
current status, and our long term plans.
Two years ago, RLL began as a two week project to build a representation
language on which the EURISKO system would be built. We soon realized
many non-trivial research issues had to be addressed before such a
general, "self-encoding" language could be constructed. We eventually
abandoned the quest for this ultimate language, satisfying ourselves with
the generality which was possible within a limited set of constraints.
The more theoritical aspects of this representation language language work
was taken up by other members of the HPP community; and their next step is
described in [MRS].
The current system plays a necessary boot-strapping role -- certain parts
of the system must be present, as these are used to fill in other parts.
For example, the code which is used to expand high level definitions must
be present -- or at least enough of it to generate the rest of the itself.
We are expanding the number and size of the knowledge bases RLL contains,
and as the magnitude and variety expand, reasoning by analogy becomes
increasingly feasible. Important in this list of knowledge bases is the
elusive "expertise about expertise." It is this knowledge which enables
RLL to fashion new ESs with greater efficiency and accuracy. The EURISKO
system, by Lenat, contains knowledge bases about elementary mathemtics,
games, heuristics, representation, and Lisp programming. There was no
extra work needed to add "heuristics" to that list, since each heuristic
was already represented the same way as, e.g., each mathematical function.
Thus the heuristics were already capable of working on each other. For
instance, a heuristic rule that said "If an operation is sometimes useful
but very timeconsuming, Then specialize it" could apply to
FunctionalComposition, but also to heuristics -- in fact, in one run of
Eurisko, it even applied to itself. Lisp programming also required no
real change in the RLL system, as each Lisp function has a unit to
represent it. While reasoning about Lisp predicates, Eurisko noticed that
EQ appeared to be a restriction of EQUAL, disjoined an EQ test onto the
front of EQUAL, to see if ran faster, and lo and behold it did! This
minor glitch in InterlispD has since been repaired. In the field of
Games, Eurisko applied the same set of heuristics as used in it other
domains to the task of designing a naval fleet of ships to be used in
wargames, and the fleet it designed won first place in the national
Traveller TCS fleet battle tournament on July 3-5, 1981. The important
idea in all this is that self-descrription and uniformity are powerful --
so powerful that they more than repay the initial cost of carefully
describing every piece of the system to itself. Having knowledge which
can be used across domains makes building expert systems easier and
easier, as that common KB grows.
While other ESBp systems have proven expedient for tackling particular
problems in particular domains, such systems seem inescapably limited in
the scope of problems they can solve. We feel this problem is intrinsic
to such ESBps, at least until they, like the human programmers they are
trying to emulate, are capable of a crude understanding of the code they
are attempting to to compose -- an understanding which is far deeper than
the superficial level any current system (including RLL) has yet achieved.
This work grew out of earlier research on automatic programming [Green et
al, 1975], and AP still seves as the "engine" that converts
self-description into self-modification. RLL was written with the goal of
attaining the necessary level undertanding to carry out such a massive
automatic programming task.
! BIBLIOGRAPHY
[Green et al 75] Progress Report on Program Understanding Systems, SAIL Memo
[Greiner80] - "RLL-1: ..."
[Greiner & Lenat80a] - AAAI
[Greiner & Lenat80b] - Details of RLL
[Lenat 81] The Nature of Heuristics, HPP Memo and Xerox Report
[Lenat, Hayes-Roth, & Waterman] - Cognitive Economy
[Smith] CORLL
[Genesereth, Greiner & Smith] - MRS